Merge Sort

April 27, 2019 3 minutes

MergeSort algorithm works on the principle of divide and conquer and achieves a better average and worst case runtime as compared to the sorting algorithms (ex: InsertionSort, SelectionSort) that we previosuly discussed.

The basic idea behind this algorithm is to divide the given input into equal halves until it cannot be further divided. Once done, we start merging these individual elements in sorted order which evantually gives us the entire datastructure in sorted order.

Consider the following example :

MergeSort

For the input dataset : {5,8,11,3,7}, it is divided into two halves in every iteration until we are left with individual elements. Once this state is reached, we start to merge those elements in sorted order.

Pseudo Code

  1. Initialize
    • input: the input array that we need to sort
    • start: the start index of the array
    • end: last index of the input array
    • length : number of elements in the input array
  2. Divide
    • if the length of input array is 0 or 1, return the same
    • else :
      • calculate mid as the middle index of start and end indices.
      • call Divide recursively for start to mid.
      • call Divide recursively for mid+1 to end.
  3. Merge
    • Create two seperate temp arrays (say left and right) to hold the two halves (start to mid and mid+1 to end).
    • Populate the two temp arrays.
    • Now compare the elements on same index from the two temp arrays and populate the input array with smaller value.
    • Once done, check if any of the two temp array still has some elements left (due to unequal lengths). If yes, populate the remaining elements.

Complexity

Dividing the input dataset can be completed in $O(log n)$ and an additional $O(n)$ comlexity to merge individual elements in sorted order. Thus the overall complexity becomes $O(n*log(n))$

Java Implementation

   private void divide(int[] input, int start, int end) {
        if (start < end) {
            int mid = (end + start) >> 1;
            divide(input, start, mid);
            divide(input, mid + 1, end);
            merge(input, start, mid, end);
        }
    }

    private void merge(int[] input, int start, int mid, int end) {
        int[] left = new int[mid - start + 1];
        int[] right = new int[end - mid];

        for (int i = 0; i < left.length; i++) {
            left[i] = input[start + i];
        }

        for (int i = 0; i < right.length; i++) {
            right[i] = input[mid + 1 + i];
        }

        int leftIndex = 0;
        int rightIndex = 0;
        int index = start;

	//commpare the values from two temp arrays and populate the input[]
        while (leftIndex < left.length && rightIndex < right.length) {
            if (left[leftIndex] < right[rightIndex]) {
                input[index++] = left[leftIndex];
                leftIndex++;
            } else {
                input[index++] = right[rightIndex];
                rightIndex++;
            }
        }

	// any remaining elements in the left array?
        while (leftIndex < left.length) {
            input[index++] = left[leftIndex++];
        }

	// any remaining elements in the right array?
        while (rightIndex < right.length) {
            input[index++] = right[rightIndex++];
        }
   }

A working java example with test case can be found here.

comments powered by Disqus