Merge Sort

See the code for merge sort at github here : https://github.com/zcoderz/leetcode/blob/main/src/main/java/sort/merge_sort/MergeX.java

The above code is taken from Robert Sedgeick (Algorithm’s 4th edition)

Merge Sort is a very important algorithm in computer science and hence I have included a page here on it.

The algorithm is really straight forward with a few quirks related to performance that I highlight below.

Here are the steps for the algorithm in very simple form:

• Divide the array into two equal halves.
• Sort the left and right half
• Merge the sorted left and right halves

Below is the main code to sort the array. Notice that if the array has less items than a certain cutoff (10) here , it is more efficient to run an insertion sort algorithm to sort the array than merge sort itself. Also note that the code checks if the first of right array is greater or equal than last of left then merging doesn’t need to occur, we can copy the source array straight into the destination array. Notice also how the code alternates source and destination arrays in repeated sort calls. Alternating the source and destination arrays in this manner circumvents the need to copy elements into an auxiliary array and thus saves time in unnecessary memory moves.

private static void sort(Comparable[] src, Comparable[] dst, int lo, int hi) {
    if (hi <= lo + CUTOFF) {
        insertionSort(dst, lo, hi);
        return;
    }
    int mid = lo + (hi - lo) / 2;
    sort(dst, src, lo, mid);
    sort(dst, src, mid + 1, hi);
    if (!less(src[mid + 1], src[mid])) {
        System.arraycopy(src, lo, dst, lo, hi - lo + 1);
        return;
    }
    merge(src, dst, lo, mid, hi);
}

Here is the code to merge the left and right arrays together. Notice that the code runs a stable sort to pick elements first from the left portion when left and right index values are equal.

private static void merge(Comparable[] src, Comparable[] dst, int lo, int mid, int hi) {
    assert isSorted(src, lo, mid);
    assert isSorted(src, mid + 1, hi);
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) dst[k] = src[j++];
        else if (j > hi) dst[k] = src[i++];
        else if (less(src[j], src[i])) dst[k] = src[j++];   // to ensure stability
        else dst[k] = src[i++];
    }
    assert isSorted(dst, lo, hi);
}