The n log n lower bound

Merge sort and heap sort take O(n log n). Could another method do better? Not if it learns about the values only by comparing them. This lesson proves it, and the proof is short.

Sorting by comparing

A comparison sort learns about the values only by asking questions of the form “is x < y?”. Every sort so far in this station is one. It may move values around however it likes, but its choices can depend only on the answers it has had.

The decision tree

So any comparison sort, run on lists of a fixed length n, can be drawn as a tree. Each box is a comparison. The answer picks the left or right branch. A leaf is reached when the sort knows the order. Step through the tree for three values:

The number of comparisons on an input is the length of its path from the top to a leaf. The worst case is the longest path: the height of the tree.

The proof

1. The values could arrive in any of n! orders. Each order needs a different rearrangement to sort it, so each must reach a different leaf. The tree has at least n! leaves.
2. Each comparison has two answers, so a tree of height h has at most 2ʰ leaves (h twos multiplied together).
3. So 2ʰ is at least n!, which means h is at least log₂(n!): the number of times n! can be halved.
4. At least half of the numbers 1, 2, …, n are n/2 or more, so n! is at least (n/2)^n/2: n/2 copies of n/2 multiplied together. Then log₂(n!) is at least (n/2) log₂(n/2), which grows like n log n. This is written Ω(n log n): Ω means “at least this fast, for large n”.

Merge sort and heap sort meet this bound, so they are optimal among comparison sorts. No comparison sort can beat them by more than a constant factor (a fixed multiple), unless it does something other than compare.

Sorting faster than the bound

The proof assumes the sort learns only from comparisons. There are two ways to do better:

• Use the values themselves. If the values are small whole numbers, they can be used as list positions. Counting sort and radix sort (lesson 6) do this and run in O(n) for suitable inputs.
• Use what you know about the input. On a nearly sorted list, insertion sort is O(n + I) (lesson 1). The bound is about the worst case over all inputs, not about every input.