Bottom-Up Merge Sort

An iterative (non-recursive) merge sort that repeatedly merges adjacent sorted runs of size 1, 2, 4, … until the whole array is sorted.

Context

Bottom-Up Merge Sort is merge sort implemented iteratively: instead of recursively splitting the array, it builds sorted runs from the bottom up by repeatedly merging adjacent runs of length 1, then 2, then 4, and so on.

The practical win is not “faster comparisons” (the asymptotic work is still O(n log n)); it’s engineering-friendly behaviour:

• No recursion ⇒ no call-stack growth (useful in languages/environments with small recursion limits or strict stack policies).
• Predictable access pattern ⇒ good locality during merging and easy to reason about performance.
• Stable by construction (when equal keys keep their original relative order), which is often a real product requirement (e.g. sorting UI rows by secondary keys).

Core idea

• Maintain a run size sz that starts at 1 and doubles each pass.
• In each pass, merge pairs of adjacent runs: [lo..lo+sz-1] with [lo+sz..min(lo+2*sz-1, n-1)].
• After a full pass, every run of length 2*sz is sorted; doubling sz preserves the invariant until the entire array is one sorted run.

Key invariant:

At the start of a pass with run size sz, the array is partitioned into consecutive sorted runs of length sz (except possibly the last, shorter run). The merge step combines two adjacent sorted runs into one sorted run of length up to 2*sz, preserving stability if ties are taken from the left run.

Implementation

class MergeSort {

    @SuppressWarnings("unchecked")
    static <T extends Comparable<? super T>> void sort(T[] array) {
        var n = array.length;
        var aux = (T[]) new Comparable[n];
        
        // sz = current run length; after each pass, runs of length 2*sz are sorted.
        for (var sz = 1; sz < n; sz *= 2) {
            for (var lo = 0; lo < n - sz; lo += sz + sz) {
                var mid = lo + sz - 1;
                var hi = Math.min(lo + 2 * sz - 1, n - 1);
                
                // Optional micro-optimisation: if already ordered, skip merge.
                // This is safe because both halves are sorted by the loop invariant.
                if (lessOrEqual(array[mid], array[mid + 1])) continue;
            
                merge(array, aux, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, n - 1));
            }
        }
    }

    private static <T extends Comparable<? super T>> void merge(T[] array, T[] aux, int lo, int mid, int hi) {
        // Precondition: array[lo..mid] and array[mid+1..hi] are each sorted.
        // Postcondition: array[lo..hi] is sorted and stable.        
        
        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++]; // stability: take left on ties
            else                                    array[k] = aux[j++];
        }
    }
    
    private static <T extends Comparable<? super T>> boolean lessOrEqual(T v, T w) {
        return v.compareTo(w) <= 0;
    }
}