Merge Sort

Introduction

Can sorting be made faster? We have seen sorting techniques like (Insertion Sort, Selection Sort and Shell Sort) which have a quadratic running time. With growing size of the inputs, it becomes tough to use these algorithms. Is there any faster alternative? We would like to find answers to these questions in the Merge Sort article.

On the other hand if you are interested in watching a video for this article, you can subscribe our Youtube Channel.

Purpose of the Article

In this article we try to answer the questions mentioned above. Yes there are many faster alternatives. And these are the ones which are widely used. A different class of algorithms, we also term them as Divide and Conquer algorithms. In most of the cases they have less than quadratic, mostly NlogN running time. In this article we will understand one such algorithm known as Merge Sort.

A word about Divide and Conquer algorithms

The basic idea involves only three steps as mentioned below:

  • Divide – the input into sub-problems.
  • Conquer – the smaller sub-problems (mostly using recursion).
  • Combine – the individual results of all the sub-problems to get the final result.

Merge Sort – A faster sorting technique

At first this algorithm may seem to be a tough one, but if we can spend some time to understand the steps involved in its implementation and working, we might get it in the first go. To start with lets assume an array A containing N elements and we will sort it using merge sort. The steps are mentioned below:

Step 1: If the length of the input i.e. N is equal to one, return the input, because if there is one element it is already sorted.
Step 2: If the length of the input i.e. N is greater than one, we divide the array in two parts A[0, N/2] and A(N/2 +1, N) and recursively sort the two parts.
Step 3: Merge the two sorted sub-lists.

Explanation and Approach

Suppose we have the below input to sort.

img1

Clearly N is equal to 8, hence according to step 2 we divide the array into the below two sub-arrays:

step1

Now recursing on both the sub-arrays individually, we again divide them further

step2

Again recursing on all the four sub arrays

step3

Now, if we analyze the above 8 sub arrays, each of them contain just one element and now according to Step 1 mentioned above, all of them are individually sorted. This precisely means that now we just have to merge all the sorted sub-arrays.

When we merge 6 and 10 the result would be a sub-array : 6 and 10
Similarly merging 13 and 5 would result in a sub-array : 5 and 13

So after the first level of merging we get four sorted sub-arrays as mentioned below:

step5

Now we merge the sorted sub-arrays 1 with 2 and sub-arrays 3 with 4 separately
The results would be two new sub-arrays as mentioned below:

step6

Now we are left with two sorted sub-arrays and we need to merge them. The result would be as below:

Result : step7

And we are done …

You must have noticed, that the major part of the algorithm is merging. So we write a merge routine first, our merge routine will take two sorted arrays and will merge them into a single sorted array and return the array. Below is the code for Merge subroutine.

Now the Merge-Sort routine is also very simple, it just divides the array into two parts and recursively calls itself, so that it can divide the array till there is one element left in each of the sub-arrays. After that it calls the merge routine passing the two sub-arrays. After completing execution it returns the final sorted array.

Below is the code for the Merge-Sort routine:

This is all about merge sort code. Let us analyze the running time of the Merge Sort algorithm.

Analysis

We will analyze the merge routine and mergeSort routine one by one :

Merge Routine

The merge routine basically traverse through the complete array once. So the running time is basically linear (i.e. traversing the array once). That means the running time for merge is directly proportional to N, that also makes sense. If we want to merge two lists, it would be good only if we visit each element once.

Merge Sort Routine.

This routine does a constant amount of work to find the mid element. It takes time proportional to the length of the input to divide the array into two parts, which is again proportional to N.

This whole thing is repeated and it is done through recursion so we will try to write a recurrence equation for the same.

Let us say that T(N) is the time taken by the algorithm to complete the sorting. Hence T(N) will be equal to the sum of time taken to merge sort both the halves and the the time taken to merge the sorted halves.
T(N) = time taken to merge sort the left sub-array + time taken to merge sort the right sub-array + time taken to merge the results. That implies:
T(N) = T(N/2) + T(N/2) + θ(N) where θ(N) is for merging. Hence this is the recurrence equation for the algorithm.
T(N) = 2T(N/2) + θ(N)

This finally results into θ(NlogN) running time. To understand how, we need to see the recurrence tree for this recurrence.
recursiontree
A simple mathematics can deduce that the height of the recurrence tree is logN . And each level will add up to CN, hence the total time taken is CNlogN or we can say Θ(NlogN).

Code and Implementation

Conclusion

We learnt that the Merge sort is relativey better way of sorting and performs better than Insertion Sort, Selection SOrt, Shell Sort etc in most of the cases.

To know more about Merge Sort, please visit the Wiki
Stay connected and stay Subscribed

  • Maheshwar

    Hi, I thought of implementing the Merge Sort without using Left and Right sub arrays.
    So, I coded it and tested… it is here….

    static void merge_sort(int arr[], int l, int r)
    {
    if(l == r)
    return;
    int m = (l+r)/2;
    merge_sort(arr, l, m);
    merge_sort(arr, m+1, r);
    merge(arr,l,m,m+1,r);
    }
    static void merge(int arr[],int s1,int e1,int s2,int e2)
    {
    int i=s1, j=s2, k=0;
    int c[] = new int[e2-s1+1];
    while(i<=e1 && j<=e2)
    {
    if(arr[i] <= arr[j])
    c[k++] = arr[i++];
    else
    c[k++] = arr[j++];
    }
    while(i<=e1)
    c[k++] = arr[i++];
    while(j<=e2)
    c[k++] = arr[j++];

    //copies the sorted elements into arr at their postions
    i=0;
    j=s1;
    while(i<=c.length-1)
    arr[j++] = c[i++];
    }

    • dharam

      Thank you for the code Maheshwar…

    • dharam

      This is throwing ArrayINdexOutOfBoundException.

  • Maheshwar

    Hi,
    Again I thought of implementing Merge method also with out any extra space…

    So, the below merge sort does not use any extra arrays like Left, Right and Result or C (as in my previous code)….
    The methods try to sort the elements in the array itself…

    if there is an array with 4 elements(first 4 elements are sorted & last 4 elements are sorted, but the whole array is not sorted).
    Now, we have to merge these two parts(first 4 elements & last 4 elements) into the same array…
    how can it look like… the code is below….

    static void merge_sort(int arr[], int l, int r)
    {
    if(l == r)
    return;
    int m = (l+r)/2;
    merge_sort(arr, l, m);
    merge_sort(arr, m+1, r);
    //merge(arr,l,m,m+1,r); //this method uses extra space
    merge2(arr,l,m,m+1,r); //this does not use extra space

    }

    static void merge2(int arr[],int s1,int e1,int s2,int e2)
    {
    int i=s1;
    int j=s2,temp,move_index;
    //Merging the two parts of the array into the same array
    while(j<=e2 && i<=e2)
    {
    if(arr[i] i)
    {
    arr[move_index] = arr[move_index-1];
    move_index–;
    }
    arr[i++] = temp;
    j++;
    }
    //printarray(arr);
    }

    }

    • dharam

      This is not getting compiled… there might be some problem. Please test it again.