Why No Comparison Sort Can Beat n log n

The comparison sort lower bound says that any sort which learns about its items only by comparing two of them needs about log₂(n!) comparisons in the worst case, which grows as n log n. This card shows where the bound comes from, using a picture of every comparison a sort could make, and why the linear-time sorts sit outside it.

Why does every fast comparison sort, merge sort, heapsort and quicksort on average, stop at n log n and never reach n? It is not that nobody has found a cleverer one. The limit belongs to comparing itself.

Take insertion sort on three distinct items a, b and c. Every comparison has two outcomes, and the next comparison the sort makes depends on the outcome. Draw that as a decision tree: each inner node is a comparison, each branch an outcome, and each leaf the order the sort settles on. A run of insertion sort on all six orders of 1, 2 and 3 printed the path each one took.

The tree has six leaves, one for each possible order, and its longest path has three comparisons, so its height is 3. It must have six leaves: if two orders ended at the same leaf, the sort would rearrange both the same way and get one of them wrong.

That gives the bound. Any comparison sort on n distinct items has a decision tree with at least n! leaves, n! being the number of orders. A tree of height h has at most 2ʰ leaves, because each level can at most double them. So 2ʰ ≥ n!, which means h ≥ log₂(n!), and h is the number of comparisons on the worst input. A run computed the bound for a few sizes.

For large n, log₂(n!) is about n log₂ n − 1.44n, so the bound is Ω(n log n): at least a constant times n log n. Merge sort and heapsort meet it up to a constant, which is why they are called optimal comparison sorts.

The bound is not a limit on sorting. Counting sort, radix sort and bucket sort never compare two items; they read each key's value and use it as an index, which tells them more than one yes-or-no answer at a time. The decision tree describes them no better than it describes a dictionary lookup, which is how they reach O(n) on the keys they suit, as Linear-Time Sorting, an earlier topic, showed. What they give up is generality: a comparison sort sorts anything with an order, and a linear-time sort only keys it can read as small integers or digits.

The bound settles a practical question, too. When a comparison sort is too slow, a faster comparison sort will not save more than a constant factor; the way out is to read the keys, sort less, or sort once.