The n log n Speed Limit

By Victor Arce

Merge sort, heapsort and quicksort all land at O(n log n)O(n log n) — linearithmic time: n times log n; the best worst-case for comparison sorts.. Is that a coincidence, or is there a wall none of them can break through? It turns out there's a wall — and you can prove it without looking at any specific algorithm.

Slide n below and watch the floor rise. The solid curve is the minimum number of comparisons any comparison sort must make; the upper line is n log₂ n.

A sort is a tree of questions

Strip a comparison sort down to its essence and all it ever does is ask yes/no questions: is a < b? Each answer steers it down one of two branches. So the whole algorithm is a binary decision tree, and a finished sort is a path from the root to a leaf — one specific verdict about the final order.

How many leaves must that tree have? The n inputs could arrive in any of n! orderings, and the sort has to handle every one differently, so it needs at least n! leaves.

Counting the height

A binary tree of height h has at most 2ʰ leaves. To fit all n! orderings we need

2ʰ ≥ n!, so h ≥ log₂(n!).

The height h is the number of comparisons in the worst case — the longest path. And log₂(n!) grows like n·log₂n (Stirling's approximation), which is why the floor and the n log₂ n line in the plot track each other. No amount of cleverness gets a comparison sort below it.

The escape hatch

The bound only applies to sorts that compare. If you can look at the values themselves — bucket them by digit or by range — you sidestep the decision tree entirely. That's exactly how counting sort and radix sort reach O(n) on the right kind of data: they don't ask "which is bigger?", they ask "where does this value belong?"

Back to Foundations