Merge sort algorithm details:

Worst-case Time Complexity: O(n log(n))

Space Complexity: O()

Merge sort example

The algorithm

Merge sort is comparison based algorithm, from the efficient sorting category. The algorithm is based on “Divide and conquer” (John Van Neumann), which means in this case, that the original collection is divided into smaller chunks. This idea can be implemented in a recursive fashion, so that the collection is divided into single elements and then re-constructed into a sorted collection. The re-construction, merging part of the algorithm is the step where the elements are ordered. In each merge stage the elements are put into the they sorted positions, in the sub collection. Breaking the original collection into it’s elements can create additional iterations(computation), and is not required. Handling the sub collections can be in place so it does not require separate collection(s).

The performance of the Merge sort algorithm is O(n log(n)) which is very impressive. I would suggest to use a default library, in a real world application as most of the languages nowadays are implementing a better performing algorithm as default sorting option. In Java the Util package contains a sort method, in the Arrays class. Based on the documentation the implementation is Dual-Pivot Quicksort which performs O(n log(n)) time complexity.

As an example, an 8 element integer collection would be sorted as follows:

Original collection: 7-2-5-1-6-4-3-8
After dividing: 7 2 5 1 6 4 3 8
Merge #1: 2-7 1-5 4-6 3-8
Merge #2: 1-2-5-7 3-4-6-8
Merge #3: 1-2-3-4-5-6-7-8

Java implementation

My implementation of the merge sort algorithm in java:

     /**
     * Merge sort comparable items in specified order
     * 
     * Time complexity: O(n log n)
     * 
     * @param items - the array holding Comparable items
     * @param isAsc - the order of sorting
     */
    public static void sort(Comparable[] items, boolean isAsc) {
        int arrayLength = items.length;
        mergeSort(items, 0, arrayLength - 1, isAsc);
    }

    /**
     * Recursive method to divide and merge array elements  
     * 
     * @param items - the array holding Comparable items
     * @param lowIndex - the lower index to start merging from
     * @param highIndex - the upper index to merge 
     * @param isAsc - the order of sorting
     */
    private static void mergeSort(Comparable[] items, int lowIndex, int highIndex, boolean isAsc) {
        if (lowIndex < highIndex) {
            int middle = lowIndex + (highIndex - lowIndex) / 2;
            mergeSort(items, lowIndex, middle, isAsc);
            mergeSort(items, middle + 1, highIndex, isAsc);
            merge(items, lowIndex, middle, highIndex, isAsc);
        }
    }

    /**
     * Merge the items
     * 
     * @param items - the array holding Comparable items
     * @param lowIndex - the lower index to start merging from
     * @param middle - the middle of the current chunk to merge
     * @param highIndex - the upper index to merge
     * @param isAsc  - the order of sorting
     */
    private static void merge(Comparable[] items, int lowIndex, int middle, int highIndex, boolean isAsc) {
        //Create the sub array
        Comparable[] helper = new Comparable[items.length];
        System.arraycopy(items, lowIndex, helper, lowIndex, (highIndex - lowIndex) + 1);
        
        int i = lowIndex;
        int j = middle + 1;
        int k = lowIndex;
        //Sort
        while (i <= middle && j <= highIndex) {
            if (isAsc && helper[i].compareTo(helper[j]) < 0 || !isAsc && helper[i].compareTo(helper[j]) > 0) {
                items[k] = helper[i];
                i++;
            } else {
                items[k] = helper[j];
                j++;
            }
            k++;
        }
        
        //Copy the rest of the sub array as is
        System.arraycopy(helper, i, items, k, (middle - i) + 1);
    }

The above code snippet is using the Comparable interface, to simplify the code. It allows to define the sorting order as ascending or descending. In the code I am using a helper array to simplify the code, to copy elements back into original array. This is not necessary with an in place merge sort, an example of this can be found here.

The complete implementation with unit tests is available in my Java Algorithms Github Repo, https://github.com/pete314/algorithms-java

 

Share This