Merge Sort

In this article, we will look at the merge sort in Java. We will discuss the merge sort algorithm and its implementation in Java.

Introduction

Like Quick Sort, merge sort is a divide and conquer algorithm. It works on the principle of dividing the problem into sub problems recursively and then combine them together to get the final output (Sorted elements). We base algorithm on the recursion technique. Let’s look at the high level flow for the merge sort algorithm in Java.

1. Mere Sort Algorithm

Before we jump in the code, let’s try to understand the basic principle of merge sort algorithm. The merge sort algorithm follows a divide-and-conquer approach.With this approach, we break the problem in to several sub-problems of smaller in size and solve the problem recursively and finally combine these solutions to create the final solution for the original problem.

The divide-and-conquer approach involves the following three steps:

  • Divide – divide the problem in to number of sub problems.
  • Conquer – Solve the sub-problems. With the divide method, the sub problem size is small enough to solve it in straightforward manner (e.g. with merger sort in Java, we create array of size 1 which is already sorted.)
  • Combine – Combine the solution of the sub-problems to solve the original solution.

The merge sort algorithm follow the same approach, here are the high level steps followed by merge sort algorithm to solve the problem:

  1. During merge sort, we divide the array or collection into two sub collections.
  2. To divide the array, we take the middle of the array and split in into left and right array.
  3. The split process will continue until we have only 1 element in the array (Since we need not sort the 1 element and this is the main concept for the merge sort algorithm.) 
  4. Once we get to the single elements, we will combine the results of the 2 arrays by comparing and putting them in sorted order.

Let’s look at the following example to understand the workflow and how this algorithm works

Merge Sort in Java

Numbers in red shows the order in which merge sort executes steps.

The recursion “bottoms out” when the sequence to be sorted has length 1, in which case there is no work to be done, since every sequence of length 1 is already in sorted order.

2. Merge Sort Pseudo Code

Before we get in the code, let’s take a look at the pseudo-code for the merge sort algorithm:

mergeSort(a[] ,l,r)

1 if l < r

2     then q  (l + r)/2

3          mergeSort(a,l,q)

4          mergeSort(a, q + 1, r)

5          Merge(a,l,q,r)

There are few important points which we should keep in mind while looking at the pseudo-code.

  1. The algorithm sort the element in sub-array A[l, r].
  2. if l >= r, the sub-array contains at most one element which is already sorted (single element will always be sorted).
  3. If #2 is not correct, we compute the index q and divide the a[l..r] into two sub-arrays (a[p..q] having n/2 element and a[q+1..r] also containing n/2 element).

3. Merge Sort in Java

Let’s see how to implementation merge sort in Java. The example contains a lot of documentation to give you a clear explanation of the logic but we will cover each steps of the algorithm. 

public class MergeSortAlgo {

    public static void main(String[] args) {

        int[] input = {24,2,45,20,56,75,2,56,99,53,12};
        int[] temp = new int[input.length];  // Temp array to store split results.
        quickSort(input, 0 , input.length-1, temp);
        
        for(int i =0; i< input.length; i++){
            System.out.println(input[i]);
        }
    }

    private static void mergeSort(int[] array, int start, int end, int[] temp){
        /**
         * We only want to split it until the start is less than the end.We don't want to go beyond
         * this point.
         */
        if(start < end) {

            // We need to find a point to split the array.We will find the midpoint.
            int mid = (start + end) / 2;

            /**
             * Now, we will split the array until it is small enough to be sorted (only one element).
             * We will split the array from the starting point till mid and from mid point till the end.
             * Please refer to the picture above to see how the split process works.
             */
            mergeSort(array, start, mid, temp);
            mergeSort(array, mid + 1, end, temp);

            /**
             * Time to sort and split back the given input.
             */
            merge(array,temp,start,end,mid);
        }
    }

    private static void merge(int[] array, int[] temp, int start, int end, int mid){

        /* Copy both side in to our temp array */
        for(int i =start ; i<= end ; i++){
            temp[i] = array[i];
        }
        // let's sort and merge back the array

        int i = start; // start will become left
        int j = mid+1;  // this is the starting point for our where right hand of the array was copied in helper
        int current = start; // position where we like to sort and merge

        /**
         * We will iterate through the temp array.Compare the right and left half , copy the smallest element from the 2 array to
         * the original array/
         */
        while(i <=mid && j <= end){
            if(temp[i] <=temp[j]){
                array[current] = temp[i];
                i++;
            }
            else{
                /**
                 * If right element is smaller than left element.
                 */
                array[current] = temp[j];
                j++;
            }
            /**
             * we increment current position only when we got a match.This can be added to both if and else sections but
             * we will keep it in a common place to avoid code duplication
             */
            current++;
        }

        /**
         * Copy rest of the left side of the array in to the target array
         */
        int remaining= mid -i;
        for (int k = 0 ; k<= remaining; k++){
            array[current+k] = temp[i+k];
        }
    }
}

Let’s try to inspect some important points

if (start < end) {
  int mid = (start + end) / 2;
  mergeSort(array, start, mid, temp);
  mergeSort(array, mid + 1, end, temp);
  merge(array, temp, start, end, mid);
}

We are performing following important task in this code

  1. We find the middle point for the input.
  2. We recursively calling the mergeSort method for the left and right side of the midpoint. (creating 2 sub arrays)
  3. Recursive method works until the start is greater than the end.
  4. Finally, we are calling merge method to which takes the input and both the sub-arrays and merge them together in the sorted fashion.
private static void merge(int[] array, int[] temp, int start, int end, int mid){

    for(int i =start ; i<= end ; i++){
        temp[i] = array[i];
    }

    int i = start; // start will become left
    int j = mid+1;  // this is the starting point for our where right hand of the array was copied in helper
    int current = start; // position where we like to start sorting and merge

    while(i <=mid && j <= end){
        if(temp[i] <=temp[j]){
            array[current] = temp[i];
            i++;
        }
        else{
            array[current] = temp[j];
            j++;
        }
        current++;
    }
    int remaining= mid -i;
    for (int k = 0 ; k<= remaining; k++){
        array[current+k] = temp[i+k];
    }
}

Our merge method sorts and merging the 2 arrays. Let’s see few important points for this method

  1. Method needs start and end point of the arrays along with the original array (we need this original array to sort the final output).
  2. Need the midpoint for both the arrays.We need this to while sorting the left and right side of the array.
  3. To keep sorting simple, we are using a temp array. We use this array to a temporary store both the sub array before our the sort and merge operation.
  4. In the while loop we iterate through the temp array and put the element in the right position in the original array.
  5. At the end of the while loop, one side is already in the right position, so we just copy the left side of the array in the target position.

4. Time Complexity

The merge sort algorithm is a recursive algorithm. We can express the time complexity as

T(n) = 2T(n/2) + O(n)

the time complexity will come to O(nLogn).Here are some additional information for the quick sort algorithm:

  • Space Complexity  – O(n) 
  • In place Sorting – Not for most of the cases.
  • Time complexity for worst, average and best cases is always O(nLogn) as merge sort always divides the array into two halves.

5. Merge Sort Applications

Here are some typical use cases where merge sort is the right choice for us.

  1. In case data structure does not support random access. We use it in many external sorting use cases.
  2. Linked list is another good example where merge sort is powerful and very quick. This is possible since it is easy to change the pointer in the linked list during the merge.
  3. You can use merge sort when you need a stable sort. It’s very important feature of merge sort.

5.1. Merge Sort Drawbacks

Though merge sort is really good algorithm, there are few drawbacks which we should keep in mind while selecting sorting algorithms for the problem.

  1. Though the Worst time complexity for the merge sort is O(nLogn), it’s still slow as compared to the quick sort.
  2. It require additional space of O(n) for temp array. This can be a big issue if we have space constraints for our application.
  3. Not a good solution for sorted input as it will go through the whole process of divide-and-conquer.

Summary

In this article, we saw the merge sort in Java. We discussed the various steps to understand the merge sort algorithm. In the end of this article, we saw when merge sort algorithm is a perfect choice for your sorting problem. You can find the source code in our GitHub repository