Lower bounds and variants

Model any comparison sort as a binary decision tree. Each internal node is one comparison a[i] < a[j]?, each leaf is one possible output order. There are n! orderings of n distinct values, and a correct algorithm needs a leaf for each, so the tree has at least n! leaves.

A binary tree with L leaves has height at least log₂ L. So some input needs at least log₂(n!) comparisons. By Stirling's approximation, log₂(n!) = n log₂ n - 1.44 n + O(log n) = Ω(n log n). Merge sort and heap sort are therefore optimal up to constant factors.

The bound only applies to algorithms that learn about the input by comparing elements. Counting, radix and bucket sort read key values directly, so they escape it.

A sorting network is a fixed sequence of compare-exchange operations, each of which puts two chosen positions in order. The sequence does not depend on the data, so all comparisons in one layer can run in parallel in hardware or on a GPU.

The 0-1 principle says a network sorts every input if and only if it sorts every input made of only 0s and 1s, which makes networks testable. The odd-even transposition network has depth n; bitonic sort has depth O(log² n) and needs O(n log² n) comparators; the optimal 4-input network uses 5 comparators in 3 layers.

1// optimal 4-input sorting network: (0,1) (2,3) | (0,2) (1,3) | (1,2)
2static void sort4(int[] a) {
3    cmpSwap(a, 0, 1); cmpSwap(a, 2, 3);
4    cmpSwap(a, 0, 2); cmpSwap(a, 1, 3);
5    cmpSwap(a, 1, 2);
6}
7static void cmpSwap(int[] a, int i, int j) {
8    if (a[i] > a[j]) { int t = a[i]; a[i] = a[j]; a[j] = t; }
9}

A stable partition moves every element satisfying a predicate to the front while keeping the relative order inside both groups. Quick sort's partition is not stable.

With O(n) extra memory it is two passes over a buffer. In place it can be done with O(n log n) rotations by divide and conquer. Java streams do this when you use Collectors.partitioningBy.

1static int stablePartition(int[] arr, IntPredicate keep) {
2    int[] tmp = new int[arr.length];
3    int w = 0;
4    for (int x : arr) if (keep.test(x)) tmp[w++] = x;     // matches first, original order
5    int boundary = w;
6    for (int x : arr) if (!keep.test(x)) tmp[w++] = x;    // then the rest, original order
7    System.arraycopy(tmp, 0, arr, 0, arr.length);
8    return boundary;
9}

Merge sort parallelises naturally: the two recursive calls are independent, so run them on different threads (fork and join) down to a size cutoff, then use the sequential sort below it.

The top-level merge then becomes the bottleneck, taking O(n) on one core. To parallelise it, split the two sorted runs into independent pieces: take the middle of the longer run, binary search its position in the other run, and merge the two resulting pairs of sub-runs on different threads. With this, the merge itself has O(log² n) span, and the whole sort has polylogarithmic span.

1class ParallelMergeSort extends RecursiveAction {
2    final int[] arr, buf; final int lo, hi;
3    ParallelMergeSort(int[] arr, int[] buf, int lo, int hi) { this.arr = arr; this.buf = buf; this.lo = lo; this.hi = hi; }
4
5    @Override protected void compute() {
6        if (hi - lo < 8192) { Arrays.sort(arr, lo, hi + 1); return; }   // sequential cutoff
7        int mid = lo + (hi - lo) / 2;
8        invokeAll(new ParallelMergeSort(arr, buf, lo, mid),
9                  new ParallelMergeSort(arr, buf, mid + 1, hi));
10        merge(arr, buf, lo, mid, hi);   // sequential merge; a co-ranking split can parallelise it
11    }
12}
13// new ForkJoinPool().invoke(new ParallelMergeSort(a, new int[a.length], 0, a.length - 1));