Merge Sort Algorithm With Examples

In this tutorial, i will show you the Merge Sort Algorithm with some examples for quick understanding. I will start by showing an example algorithm of how to:

1. Merge two sorted list into one list
2. Merge two list in a single array

Once we have finished with learning the merging algorithm, i will then show you how to use the techniques learnt so far for Merge sort algorithm with some examples.

As for Merge sort algorithm, i will show:

1. Iterative Merge Sort (Or Two Way Merge Sort) with an example, and
2. Recursive Merge Sort (Divide and Conquer procedure) with an example

Merge two sorted list into one list

For this i will show how to merge the two sorted list (array A and array B) shown in the image below into Array C.

For array A i have m elements and my m elements equals 5 elements and for Array B i have n elements and my n elements equals 4 elements. These two list may or may not have same no. of elements – it doesn’t really matter, but each least must have a minimum of least one element.

Note that merge sort is a comparison sort and so we are going to be comparing A[i] to B[j]; if A[i] is less than B[j], we place A[i] in C[k] and increment i and k otherwise we place B[j] in C[k] and increment j and k where i, j,k are all counter variables.

So initially i, j, k all have to point to the starting indices A, B, C by initializing them to 0.

So starting from the initial position of i, j and k, compare A[i] to B[j], A[i] is less than B[j]; so copy A[i] to C[k] and increment i and k by 1 so that the can point to the next index.

We move the pointer to the next index so that we know the next element in the list to be compared. We also move the pointer of array C to the next index after every insert so that we know where to insert the next element.

Next compare A[i] (please note where i is now from the image above) with B[j], B[j] is lesser than A[i] so place B[j] in C[k] and move both j and k to next index.

What i will ask you to do is to continue with the comparison using the image above and moving the right pointers each time as you copy an element from either A or B into C and you should arrive at what i have in the image below.

Now notice that both indices of array A and B are now pointing to the last element in each array.

So again we compare A[i] with B[j], A[i] is lesser; so copy A[i] to C[k] and increment i and k. i therefore becomes 5.

Now if you observe, one of the list has finished (i.e A) but there is one element in the second list that is not in C. And for sure if you have two list which you are to merge and one list is larger than the other, then you should expect this to happen.

So what you then have to do is to copy all remaining elements in the larger list to C directly. There is no fear of whether C will still be sorted because remember that both A and B are sorted list and whatever elements remain in either A or B in your own situation will already be sorted in the correct order – take some time here to observe what i just said. j and k then points to the next index in both B and C – of course there is no such next index in either B or C, so we are done.

Algorithm To Merge Two Sorted List

So the merge function will take two arrays as parameters A[] and B[] and also take m which is the size of A and n which is the size of B.

We also need i, j and k to all point to the starting index of A, B and C as stated earlier.

Next is to write the comparison code and which ever is lesser i copy from either A or B to C and increment either i and k or j and k depending from which array i copied from.

Notice that i have combined both the copying and the incrementing of i and k or j and k at the same time with the code C[k++] = A[i++] or C[k++] = B[j++].

This process has to continue, how long? Until either A or B has finished processing it elements (i.e until either i < m or j < n). I will therefore wrap the comparison code inside a while loop.

In our situation, after the loop terminates we still have an element left in B that has not been copied to C. We will copy all elements from the current position of i and j to c and will set the code in such a way that only the list that is yet to be exhausted will trigger the copy.

i am not initializing i or j so that the copy starts from the current position of i or j to avoid copying elements that have already been copied. Only one of the for loops will execute depending on which of A or B still have elements yet to be copied to C.

So this is all about merging two sorted list into one list.

Merge Two Sorted Array Time Complexity

Because we are copying m elements from A and n elements from B, the time taken to merge two sorted array is O(m + n).

Merge Two List in a Single Array

I have put two list in a single array to show you how to merge them. This will become more clear and very useful to you when we get to merge sort algorithm proper.

From elements 2 to 12 (index 0 to 3) is one list (observe that they are sorted) and from elements 3 to 10 (index 4 to 7) is another list (also sorted). Please ignore the code for now.

I want to merge both list into a single array B and then copy the elements from B back to A. Let us call the first index in A as low represented by L and the last index in A as high represented by h. Also let us call the element before the divider as middle represented by mid and the first element after the divider we will represent as mid + 1. So the first list is from L to mid and the second list is from mid + 1 to h.

For merging the two list i have to create another array B of the same size as already stated.

So we will use the same procedure as before, and so for that i will re-introduce i, j and k.

So if you follow same procedure as before, what you should have after sorting is as show below

So from what you can see, we can merge two sorted list in a single array into an extra or auxiliary array and copy the result back to the original list. Again you can see that we need to create extra memory or space to store the merged array before copying them back to the original array – hence the merging algorithm is not an in-place sorting algorithm.

Now we can modify our original merging algorithm to fit this two list in a single array i have been explaining.

So as you can now see, for the modified algorithm, i need just array A as input parameter, and i also need low L, middle mid and high h parameters.

void Merge(int A[],int l,int mid,int h)

Then we declare i, j and k as integer variables like before but this time it should not be initialize to 0. i should be initialized to 0 and j should be initialized to mid + 1. K also should be initialized to L.

void Merge(int A[],int l,int mid,int h)
{
int i=l,j=mid+1,k=l;

Then we create an auxiliary array with same size as A (may be larger than A if you are not bothered about space).

void Merge(int A[],int l,int mid,int h)
{
int i=l,j=mid+1,k=l;
int B[h + 1];

Notice that i have used h + 1; the index h has the value 7 because i am using a zero based indexed but the actual elements in our array is 8; this is the reason for the +1.

Also notice that our while loop has to change from i < m to i <= mid and j < n becomes j <= h.

Also the comparison statement has to change from if(A[i]<B[j]) to if(A[i]<A[j]). C[k++]=A[i++]; inside the if statement changes to B[k++]=A[i++]; and C[k++]=B[j++]; in the else statement changes to B[k++]=A[j++];

Some code inside the for statements should also change and i will leave that for you to handle to test yourself to see if you have been following. In any case, what we now have after all modification is as shown below.

void Merge(int A[],int l,int mid,int h)
{
    int i=l,j=mid+1,k=l;
    int B[h + 1];
    while(i<=mid && j<=h)
    {
        if(A[i]<A[j])
            B[k++]=A[i++];
        else
            B[k++]=A[j++];
    }
    for(;i<=mid;i++)
        B[k++]=A[i];
    for(;j<=h;j++)
        B[k++]=A[j];
    for(i=l;i<=h;i++)
        A[i]=B[i];
}

The last for loop is used to copy all elements from array B back to array A.

Before i continue note that when i am explaining merge sort, i will not be explaining merging anymore – i will just go ahead and use my final code for Merge in merge sort.

So now let’s discuss Merge Sort Algorithm and i will start with Iterative Merge Sort.

Iterative Merge Sort (Two Way Merge Sort)

There are two kinds of merge sort, Two way merge sort and merge sort. Two way merge sort is an iterative or repeating procedure algorithm using loop, while merge sort is a recursive procedure algorithm. So with two way merging, you can merge two list at a time (there is also m way merging where you can merge more than two list at a time).

So given a list as shown below, an array having 8 elements and the list is not sorted,

how do i sort them using merge sort? How can i merge them when i need at least two sorted list for merging. What i can do is: i will assume that each element in the array is a list; therefore what i have is 8 list with 1 element in each list – each list has a single element; and if each list has a single element, it means it is already sorted; so now can we merge them? yes, i have to merge 8 list into a single sorted list using two way merge method.

So i start with the first and the second list. What i have to do is compare both element as usual and if the first element is greater than the second element, swap their positions.

So now for the first two elements we now have a single list with 2 elements. Next i compare 7 and 5 and sort and merge them accordingly and now i have another two list merged into a single list.

So i continue same procedure for the remaining 4 list and now i have 4 new list in total (no more 8)

Now that i have completed merging the 8 list into 4, the first pass is completed. Note that if there where 9 elements, the 9th element will not have an element to pair with for the first pass but can be merged later on – maybe when the 4 lists are eventually merged into 1 list, then we can merge the 1 list of 8 elements with 1 list of 1 element (i.e that 9th element).

So if i do the same procedure all over again, my 4 lists of 2 elements each will then be merged into 2 lists of 4 elements each and with this i have completed the second pass.

So i repeat the same procedure and my 2 list of 4 elements each is now merged into a single sorted list and with that i have completed the third pass.

2 way merge sort time complexity

The time complexity of 2 way merge sort is O(nlogn). Let us do some analysis to see why.

So we are merging n elements in each pass (note that our n no. of elements for our particular example is 8). So we merge 8 elements in each pass and we have 3 passes and each pass 8 elements was divided by 2 until we arrived at only 1 list (see attached image for the equation 8/2/2/2=1 which becomes 8/2³=1 which becomes 8=2³ which becomes log₂8=3).

So from our derived equation, we can see that no. of passes 3 = log₂8; replace the 8 in the equation with n no. of elements (since in reality we will not always have 8 elements – so let’s assume n elements instead) and we will see that no. of passes = log₂n or logn for simplicity.

So our time complexity will be No. of elements in the list n * no. of passes logn which is nlogn or O(nlogn).

Recursive Merge Sort (Divide and Conquer Procedure)

The divide and conquer strategy says that if a problem is large, then break the problem into sub-problems and solve them; then combine the solutions of the sub-problems to get the solution of the large problem.

So given a list of elements to sort, if a list contains a single element; we refer to it as a small problem but if the list contains more than one element, we refer to it as a large problem – Such a list has to be broken up until we get only single elements. Remember that single elements are considered sorted – once we have divided all elements into single elements, we can then merged them into one single list of sorted elements.

So basically there are two parts to the recursive merge sort divide and conquer strategy. Spliting of elements into single elements and then merging of elements into a single sorted list.

Let me first of all show you the algorithm in c language and then use the algorithm to explain the procedure.

Merge Sort Algorithm in c

#include <stdio.h>
#include<stdlib.h>

void Merge(int A[],int l,int mid,int h){
    int i=l,j=mid+1,k=l;
    int B[100];
    while(i<=mid && j<=h)
    {
        if(A[i]<A[j])
            B[k++]=A[i++];
        else
            B[k++]=A[j++];
        }
        for(;i<=mid;i++)
            B[k++]=A[i];
        for(;j<=h;j++)
            B[k++]=A[j];
        for(i=l;i<=h;i++)
            A[i]=B[i];
    }
    void MergeSort(int A[],int l,int h){
    int mid;
    if(l<h)
    {
        mid=(l+h)/2;
        MergeSort(A,l,mid);
        MergeSort(A,mid+1,h);
        Merge(A,l,mid,h);
    }
}

int main(){
    int A[]={9, 3, 7, 5, 6, 4, 8, 2},n=8,i;
    MergeSort(A,0,n);
    for(i=0;i<8;i++)
        printf("%d ",A[i]);
    printf("\n");
    return 0;
}

So recursive merge sort takes 3 parameters: the list to be sorted A[], the beginning of the list (Low) denoted as l and the End of the list (High) denoted as h.

So first we check if l < h, if true; then we know there are at least 2 elements (i.e the list is large) in the list (please note that l and h refers to the index values not the elements values), and if l == h it means there is only a single element in the list – so the list is now small.

So if l < h execution enters into the if block and then first of all divides the list into two parts with the code:

mid=(l+h)/2;

Immediately after dividing the problem into two parts, the function makes a recursive call to itself:

MergeSort(A,l,mid);

The first time this MergeSort was called it took these parameters: A[], l, h. But for the second call and so forth, notice that the parameter high h which was initially at index 8 has become mid because the initial list has been divided into two part and the middle part of the first part of the divided list has become h at index 4. We follow this procedure because we must divide the big problem into sub-problems – we need mid to divide the big list in the center each time until we have only single elements or lists.

Please note that in this recursion procedure, the code execution will not go pass MergeSort(A, l, mid) until it has finished dividing all the elements of the left part of the list (i.e from index 0 to 4) into single list with element 8. Picture it this way: each time the list is divided into 2 parts; the right part and the left part. My point is that each time the list is divided into 2 parts, the recursion call MergeSort(A, l, mid) is called only on the left list; this continues until the list has been divided into 2 list only A = {8} and A = {2}, then the function MergeSort(A, mid+1, h) is called on the right list 2.

Let’s look at this more carefully for proper understanding. Given the list as shown in the image below:

At first l == 0, h == 7 and l < h, so it calls mid=(l+h)/2 and mid == 3 so it divides the list into 2 parts from index 0 to 3 and then the function MergeSort(A, l, mid) is called on the left list A = {8, 2, 9, 6}.

Again l == 0, h == 3 and l < h, so mid=(l+h)/2 and mid == 1 so it divides the list into 2 parts again from index 0 to 1 and then the function MergeSort(A, l, mid) is called on the left list A = {8, 2}

Now l == 0, h == 1 and l < h, so mid=(l+h)/2 and mid == 0 so it divides the list into 2 parts again index 0 and index 1 thereby making them 2 singular elements or list. The function MergeSort(A, l, mid) is called on the left list A = {8}.

Now l == 0 and h is also 0 l is now equal to h and so the flow will not enter the if block and the recursion calls on the left list terminates and execution returns one step backwards to the calling function which is the block on the image marked 0, 1. At this juncture, execution will then go on the right hand side to perform merge sort on the list A = {2} and so it calls on the function MergeSort(A, mid+1, h).

As execution calls on MergeSort(A, mid+1, h), it finds that l is not less than h because remember that when the recursion calls on the left part terminated, execution went backwards by 1 step to the point where l was equal to 0, h was equal to 1 and mid was equal to 0; so h == 1 at the moment, and l = mid + 1 now also equals 1 since mid is also 0 at the moment. So since l is not less than h, the call to MergeSort(A, mid+1, h) terminates. Now both left hand and right hand calls of the function MergeSort on the list A = {8, 2} are finished and now merging has to be done and so the program calls on the merging function Merge(A,l,mid,h).

So now that the program has called on merge function, the two list A = {8} and A = {2} are merged (i will not bother explaining merge again. refer to merge section above to refresh). After merging what we now have is single sorted list of 2 elements A = {2, 8}.

Now that the first merging is finished, what does the program do next? Again it returns one step backwards to the calling function i.e to where l == 0, h == 3 and mid == 1 and from there makes a call to MergeSort(A, mid+1, h) on the right list from index 2 to 3 i.e single list of two elements A = {9, 6}.

So go ahead and continue with the procedure by yourself and see if you get same result as the image below after merging all elements on the left part of our original list i.e from index 0 to 3. Just remember this: MergeSort left, MergeSort right and when both are completed, call Merge.

So if you got it right, you should get a single sorted list of 4 elements A = {2, 6, 8, 9} as shown above. Do same procedure for the 4 elements in the right side of our original list and you should now have 2 list of 4 elements each i.e A = {2, 6, 8, 9} and A = {5, 3, 7, 4}.

MergeSort left and MergeSort right are finished at this point and then program calls on Merge to merge the two sorted list into 1 sorted list of 8 elements i.e A = {2, 3, 4, 5, 6, 7, 8, 9}

So in all there are seven merge calls (as seen in the above image) to produce the single list of sorted elements.

The time complexity for recursive merge sort is same as the time complexity of iterative merge sort i.e O(nlogn) and there is no best case or worst case time complexity for merge sort – therefore O(nlogn) is the average case time. One more thing, merging is done in post order i.e left, right then root, left, right then root, left, right then root and so on till all elements are merged into a single sorted list of n elements.

Merge sort requires extra space and the extra space it requires in n + logn.