Why Is O(n log n) the Lower Bound for Comparison Sorting?
No comparison sort can beat O(n log n). Learn the decision-tree proof behind the sorting lower bound and why non-comparison sorts can go faster.
On this page +
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 nine others run step by step, with live pseudocode and comparison counters.
Launch the visualiser Software engineer at a stealth-stage startup, and previously a front-end engineer for around a year and a half.