Top-Down Merge Sort

A stable divide-and-conquer sort that recursively splits an array, then merges sorted halves using a single auxiliary array.

Context

Merge Sort is a divide-and-conquer sorting algorithm: recursively split the array into halves until each subarray has size 0 or 1 (already sorted), then merge the sorted halves back. Two properties make it especially useful in real systems:

• Predictable performance: O(n log n) comparisons/moves in the worst case (unlike quicksort’s worst-case O(n²)).
• Stability (when implemented carefully): equal keys preserve their original relative order—important for multi-key sorting (e.g., sort by last name, then stable-sort by first name).

Core idea

• Allocate one auxiliary array once and reuse it for every merge (avoids per-merge allocations).
• Recursively sort [lo..mid] and [mid+1..hi].
• Merge the two sorted halves back into the original array by reading from aux and writing to array.

Key invariant:

• Before merge(array, aux, lo, mid, hi) runs, both halves are sorted:
  • aux[lo..mid] is sorted
  • aux[mid+1..hi] is sorted
• The merge loop maintains: after each step k, array[lo..k] contains the smallest (k-lo+1) elements of the two halves in sorted order.

Implementation

class MergeSort {

    @SuppressWarnings("unchecked")
    public static <T extends Comparable<? super T>> void sort(T[] array) {
        var aux = (T[]) new Comparable[array.length];
        sort(array, aux, 0, array.length - 1);
    }
    
    private static <T extends Comparable<? super T>> void sort(T[] array, T[] aux, int lo, int hi) {
        if (hi <= lo) return;
        var mid = lo + (hi - lo) / 2;
        sort(array, aux, lo, mid);
        sort(array, aux, mid + 1, hi);
        
        if (lessOrEqual(array[mid], array[mid + 1])) return; // optimization for already sorted halves
        
        merge(array, aux, lo, mid, hi);
    }
    
    private static <T extends Comparable<? super T>> void merge(T[] array, T[] aux, int lo, int mid, int hi) {
        System.arraycopy(array, lo, aux, lo, hi - lo + 1);
        
        int i = lo;
        int j = mid + 1;
        for (var k = lo; k <= hi; k++) {
            if (i > mid)                           array[k] = aux[j++];
            else if (j > hi)                       array[k] = aux[i++];
            else if (lessOrEqual(aux[i], aux[j]))  array[k] = aux[i++]; // keeps it stable
            else                                   array[k] = aux[j++];
        }
    }
    
    private static <T extends Comparable<? super T>> boolean lessOrEqual(T a, T b) {
        return a.compareTo(b) <= 0;
    }
}