Why Is O(n log n) the Lower Bound for Comparison Sorting?
It is one of the most beautiful results in computer science: no comparison-based sorting algorithm can do better than O(n log n) in the worst case. This is not a limitation of our cleverness — it is a mathematical certainty. Here is the intuition behind the proof, explained without heavy notation.
The decision-tree model
Picture every comparison sort as a binary decision tree. Each internal node asks 'is A less than B?', and each branch leads to the next comparison. Every leaf represents one possible final ordering of the input. To sort correctly, the tree must have a distinct leaf for every possible permutation of n elements — and there are n! permutations.
Counting the comparisons
A binary tree with at least n! leaves must have a height of at least log2(n!). The height of the tree equals the number of comparisons in the worst case, because the longest root-to-leaf path is the worst input. By Stirling's approximation, log2(n!) is approximately n log n. Therefore any comparison sort needs at least O(n log n) comparisons in the worst case.
How non-comparison sorts escape
The proof only applies to algorithms that learn about the data through comparisons. Counting Sort and Radix Sort sidestep it entirely by using values as array indices, reaching O(n + k) and O(nk) respectively. They do not contradict the theorem — they simply are not comparison sorts.
Frequently asked questions
Can a sorting algorithm be faster than O(n log n)? +
What is the lower bound for comparison sorting? +
See it in motion
Watch this algorithm and 9 others run step by step in our free interactive visualizer.
▶ Launch Visualiser