How Fast Can Sorting Be?

The comparison lower bound

A comparison sort learns about the data *only* by asking "is a < b?". Surprisingly, that question alone limits how fast any such sort can be: no comparison sort can beat Ω(n log n) in the worst case. Merge sort and a well-tuned quicksort are therefore essentially optimal among comparison sorts.

The intuition is a decision tree. Each comparison has two outcomes, so a tree of yes/no answers of height h can distinguish at most 2^h cases. To sort n elements you must tell apart all n! possible orderings, so you need 2^h ≥ n!, i.e. h ≥ log2(n!). And log2(n!) grows like n log n — that's the wall, no heavy proof required.

Decision tree to sort 3 elements a, b, c (each leaf = one ordering):

                a<b ?
              /       \
           yes          no
          b<c?          a<c?
         /    \        /    \
     a<b<c   a<c?   b<a<c   b<c?
            /   \          /   \
        a<c<b  c<a<b   b<c<a  c<b<a

  3! = 6 leaves -> tree must be tall enough; height ~ log2(6).

Beating the wall without comparing

The wall only binds sorts that *compare*. If you instead use the keys themselves as indices, you escape it. Counting sort sorts n integers in the range 0..k by counting how many times each value appears, then writing them out in order — O(n + k), no comparisons at all.

// counting sort for values in [0, k]
void countingSort(int a[], int n, int k) {
    std::vector<int> count(k + 1, 0);
    for (int i = 0; i < n; i++) count[a[i]]++;   // tally each value
    int idx = 0;
    for (int v = 0; v <= k; v++)                 // write back in order
        while (count[v]-- > 0) a[idx++] = v;
}

Heapsort: O(n log n) in place

Among comparison sorts there's one more worth knowing: heapsort. It builds a heap (a tree-shaped priority structure you'll meet in the next rung) from the array, then repeatedly pulls out the maximum and shrinks the heap. It's O(n log n) worst case — matching merge sort's guarantee — and in place, using O(1) extra space.

1. Merge sort: O(n log n) always, stable, O(n) space.
2. Quicksort: O(n log n) average / O(n^2) worst, not stable, in place, fastest in practice.
3. Heapsort: O(n log n) worst, not stable, in place — a worst-case guarantee with O(1) space.
4. Counting / radix sort: O(n + k) / O(d·(n+base)), but only for small-integer keys.

Putting it together

So "how fast can sorting be?" has two answers. If all you can do is compare, Ω(n log n) is the floor and merge/quick/heap sort sit right on it. If your keys are structured — small integers — you can drop to linear time by counting instead of comparing.

Next rung leaves linear data behind: we branch out into trees, the heap that powers heapsort, and graphs — and recursion comes right along with us.