MergeSort Algorithm

It works by dividing the input array into two halves, then recursively divide the sub arrays also into two halves and continue this process until further division of sub arrays is not possible, then start merging sub arrays in sorting order.

This can be visualized as a top-down approach when dividing the input array, then bottom-up approach for merging the smaller arrays in sorting order. At a high level, below are the steps involved in this algorithm.

• If the given input array length is n, divide the input array into two halves, with one halve with elements from [1,..... n/2] and other halve with elements from [n/2+1,........n].
• Repeat above step further dividing sub arrays also into two halves recursively until further division is .
• Then, start merging back the sub arrays in sorting order.

Steps involved in this implementation.

1. Given a non empty array input, find the middle index of the array using mid = left + (right - left) / 2;,

Note: We are getting middle index using left + (right-left)/2 formula to avoid integer overflow problem, in case if input array length is Integer.MAX_VALUE.

2. Divide input array into two halves, so the two sub arrays will become [left,... ,mid] and [mid+1,... ,right].
3. Repeat above two steps in a recursive loop until the sub arrays can't be divided further.
4. When it reaches the end, call merge() procedure which will merge sub arrays back in sorting order using below steps.
• Merge procedure takes input as
  • input array
  • left index
  • right index
  • middle index - where to split the input array, to get the desired left and right sub arrays.
• STEP 1:
  Create two temporary arrays, call it leftArray and rightArray to hold left and right sub array elements, and then copy from left to mid(inclusive) indices to leftArray and copy from mid+1 to right indices to rightArray.
• STEP 2:
  Start comparing elements from leftArray and rightArray and place them back into input array in the sorting order.
• STEP 3:
  At the end copy any remaining elements from leftArray or rightArray back to input array.

package io.cscode.algorithms.sorting;

/**
 * MergeSort implementation
 */
public class MergeSort {

    /**
     * Entry method this sorting algorithm
     *
     * @param nums input array
     */
    public void sort(int[] nums) {
        if(nums == null || nums.length==0 ||nums.length==1) {
            return;
        }
        mergeSort(nums, 0, nums.length-1);
    }

    /**
     * Main function that divides array into two halves and recursively calls itself on sub arrays
     * when the array cannot be split further, it calls merge() method to start merging on sub arrays.
     *
     * @param nums input array
     * @param left start index
     * @param right end index
     */
    private void mergeSort(int[] nums, int left, int right) {
        if(left < right) {
            int mid = left + (right-left)/2;
            mergeSort(nums, left, mid); //sort from 1...n/2
            mergeSort(nums, mid+1, right); //sort from (n/2)+1 ...n
            merge(nums, left, mid, right); //call merge function when input array can't be split be further
        }
    }

    /**
     * merge function to merge two sub arrays in sorting order.
     *
     * @param nums input array
     * @param left left index
     * @param mid mid index
     * @param right right index
     */
    private void merge(int[] nums, int left, int mid, int right) {
        int n1= mid -left +1; // mid inclusive and indexes starts with 0, so +1
        int n2 = right - mid;

        int[] leftArray = new int[n1]; // left sub array
        int[] rightArray = new int[n2]; // right sub array

        for (int i=0; i<n1; i++) {
            leftArray[i] = nums[left+i]; // copy from left to mid onto left sub array
        }

        for (int j=0; j<n2; j++) {
            rightArray[j] = nums[mid+1+j]; // copy from mid+1 to right onto right sub array
        }

        int i=0; // counter to keep track of index for leftArray
        int j=0; // counter to keep track of index for rightArray

        for (int k=left; k <= right; k++) {
            if(i<leftArray.length && j<rightArray.length) {
                if(leftArray[i] <=rightArray[j]) {
                    nums[k] = leftArray[i];
                    i++;
                } else {
                    nums[k] = rightArray[j];
                    j++;
                }
            } else {
                //copy any remaining elements in leftArray or rightArray into input array
                if(i < leftArray.length) {
                    nums[k] = leftArray[i];
                    i++;
                }
                if(j < rightArray.length) {
                    nums[k] = rightArray[j];
                    j++;
                }
            }
        }

    }

}

Complexity analysis:

To sort an array of n elements MergeSort runs in O (n log n) time in average case, best and worst cases and in terms of space it takes O(n) space in merge() procedure. One of the advantage with this algorithm is it gives consistent performance.

MergeSort implementation source code can be found here on GitHub link for Java code and JUnit tests can be found under GitHub link for Unit tests code