Scribd
Upload
13 views9 pages

Algorithm 5

Merge Sort is a sorting algorithm that recursively divides an array into two halves, sorts each half, and merges them back into a sorted sequence. The algorithm consists of two main functions: MergeSort() for dividing the array and Merge() for combining the sorted halves. An example illustrates the step-by-step process of sorting an array of ten elements using Merge Sort.

Uploaded by

angelina54320291
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
13 views9 pages

Algorithm 5

Merge Sort is a sorting algorithm that recursively divides an array into two halves, sorts each half, and merges them back into a sorted sequence. The algorithm consists of two main functions: MergeSort() for dividing the array and Merge() for combining the sorted halves. An example illustrates the step-by-step process of sorting an array of ten elements using Merge Sort.

Uploaded by

angelina54320291
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Algorithm Design & Analysis

CSE 2103
Lecture 5
Merge Sort
2

⚫ A sort algorithm that splits the items to be sorted


into two groups, recursively sorts each group, and
merges them into a final, sorted sequence.
⚫ Two functions are involved in this algorithm.
⚪ The MergeSort() function recursively calls itself to divide the
array till size becomes one.
⚪ The Merge() function is used for merging two halves.
Example
3
Example
4

⚫ Problem : Consider the array of elements a[1:10] =


(310, 285, 179, 652, 351, 423, 861, 254, 450, 520).
Solution :
1. (310, 285, 179, 652, 351 || 423, 861, 254, 450, 520)
2. (310, 285, 179 || 652, 351 || 423, 861, 254, 450, 520)
3. (310, 285 || 179 || 652, 351 || 423, 861, 254, 450, 520)
4. (310 || 285 || 179 || 652, 351 || 423, 861, 254, 450, 520)
5. (285, 310 || 179 || 652, 351 || 423, 861, 254, 450, 520)
6. (179, 285, 310 || 652, 351 || 423, 861, 254, 450, 520)
7. (179, 285, 310 || 351, 652 || 423, 861, 254, 450, 520)
8. (179, 285, 310, 351, 652 || 423, 861, 254, 450, 520)
Example
5

9. (179, 285, 310, 351, 652 || 423, 861, 254 || 450, 520)
10. (179, 285, 310, 351, 652 || 423, 861 || 254 || 450, 520)
11. (179, 285, 310, 351, 652 || 423 || 861 || 254 || 450, 520)
12. (179, 285, 310, 351, 652 || 423, 861 || 254 || 450, 520)
13. (179, 285, 310, 351, 652 || 254, 423, 861 || 450, 520)
14. (179, 285, 310, 351, 652 || 254, 423, 450, 520, 861)
15. (179, 254, 285, 310, 351, 423, 450, 520, 652, 861)
Tree of calls of Merge Sort (1,10)
6
Merge Sort Algorithm
7
Merge Sort Algorithm
8
9

THANK YOU

You might also like