Merge Sort

Merge Sort

by MSufiyanAG (for better understanding of the article, please refer to its implementation).

Merge Sort is a divide and conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge_sort() method is used to divide the array into two halves, and the merge() method is used for merging two halves.

This implementation uses a recursive approach. To better understand the algorithm, let's trace the program with example we took.

for a[]= {8, 1,10,5,4,2,7,3} , merge_sort(a,0,7) is called.

the first check happens (0<7), then

mid=0+7/2=3 merge_sort(a,0,3)
(0<3) is checked, then

mid=0+3/2=1 merge_sort(a,0,1)
(0<1) is checked, then

mid=0+1/2=0 merge_sort(a,0,0)
which is a single element, so it issues a call to terminate and it goes back to the previous call.

So, until now merge_sort(a,l,mid) was being called, but now the algorithm will call merge_sort(a,mid+1,h).

merge_sort(a,1,1)
which is a single element, so it issues a call to terminate and it goes back to the previous call.

Now, the algorithm begins the merging process, i.e. calling of merge(a,l,mid,h)

merge(a,0,0,1)
a comparison takes place and new result becomes {1,8}, which is stored in b.

Then, it goes to the previous call: merge_sort(a,2,3) (2<3) is checked, then mid=2+3/2=2 merge_sort(a,2,2)
which is a single element, so it issues a call to terminate and it goes back to the previous call. merge_sort(a,3,3) which is a single element, so it issues a call to terminate and it goes back to the previous call.

Now, the algorithm begins the merging process, i.e. calling of merge(a,l,mid,h) merge(a,2,2,3)
a comparison takes place and new result becomes {5,10}, which is stored in b.

Then, it goes to the previous call, and the algorithm begins the merging process, i.e. calling of merge(a,0,1,3) and new result is {1,5,8,10}.

Similarly, for the second part, calling of merge(a,4,5,7) and the new result is {2,3,4,7}.

Going forward, the calling of merge(a,0,3,7) and the new result is {1,2,3,4,5,7,8,10}

Here, merge(a,0,3,7) can be seen as an example of how the method works: i=k=0 j=4 while (i<=4 && j<=7)

• comparing 1st element and 5th element, i & k or j & k is incremented
• comparing 2nd element and 6th element, i & k or j & k is incremented
• comparing 3rd element and 7th element, i & k or j & k is incremented
• comparing 4th element and 8th element, i & k or j & k is incremented

The other 2 for loops are to check if the list has been divided into uneven parts i.e. 4 & 5; when we try to merge, we compare up to 4th element and 5th element is inserted without comparison, since there is nothing to compare.

The last loop is to copy b to a.

Merge sort

                      0-----7
                     /      \
                  0--3       4---7 (2 arrays)
                 /   \      /     \
              0--1  2--3    4--5   6--7 (4 arrays)
             /  \   /  \    /  \   /  \
           0,0 1,1 2,2 3,3 4,4 5,5 6,6 7,7 (8 elements)

Merging

 8  1  10  5  4  2  7  3
 \  /  \   /  \  /  \  /
 1,8   5,10    2,4  3,7
 \        /    \      /
  1,5,8,10     2,3,4,7 
     \            /
    1,2,3,4,5,7,8,10