Symptom

Every general-purpose sort in every standard library is $O(n \log n)$. Timsort, introsort, pdqsort, merge sort, heapsort. Decades of work by extremely motivated people, an enormous amount of money riding on it, and they all land on the same exponent.

That is not a coincidence, and it is not a failure of imagination. It is a proof.

Meanwhile someone on your team points out that radix sort is $O(n)$ and asks why the standard library doesn’t just use that. The answer is interesting and it is not “radix sort is impractical.”

Statement

Any sorting algorithm that gains information about the input only by comparing pairs of elements requires $\Omega(n \log n)$ comparisons in the worst case.

Every deterministic comparison sort makes at least $\lceil \log_2 (n!) \rceil = n\log_2 n - n\log_2 e + O(\log n)$ comparisons on some input.

The qualifier comparison is the entire content of the theorem, and nearly every misunderstanding of it is a failure to notice that word. This bound constrains a model of computation, not the problem of sorting.

Argument

Model any comparison sort as a decision tree. Each internal node is a comparison “is $a_i < a_j$?”, each of the two edges is an outcome, and each leaf is a final permutation the algorithm outputs. Running the algorithm is walking one root-to-leaf path, so the number of comparisons in the worst case is the tree’s height.

Step 1: the tree needs at least $n!$ leaves. There are $n!$ possible orderings of $n$ distinct elements. If two different orderings led to the same leaf, the algorithm would emit the same permutation for both — and that permutation sorts at most one of them. So the algorithm would be wrong on the other. Distinct inputs need distinct leaves. This is pigeonhole (T001) with permutations as the items and leaves as the boxes.

Step 2: a binary tree of height $h$ has at most $2^h$ leaves. Induction, or just observe that each comparison at best halves the candidate set.

Putting them together: $2^h \ge n!$, so

$$h \ge \log_2(n!)$$

Step 3: $\log_2 (n!) = \Theta(n\log n)$. This is the step that costs the post its L1, and it is done with a trick rather than Stirling’s approximation, which would be a heavier tool than needed. Keep only the largest half of the factors:

$$n! = n(n-1)\cdots\left(\frac{n}{2}\right)\cdots(2)(1) \;\ge\; \underbrace{\frac{n}{2} \cdot \frac{n}{2} \cdots \frac{n}{2}}_{n/2 \text{ terms}} = \left(\frac{n}{2}\right)^{n/2}$$

because each of the top $n/2$ factors is at least $n/2$, and the remaining factors are at least 1. Take logs:

$$\log_2(n!) \;\ge\; \frac{n}{2}\log_2\frac{n}{2} = \frac{n}{2}\log_2 n - \frac{n}{2} = \Omega(n\log n)$$

And the matching upper bound is immediate, since $n! \le n^n$ gives $\log_2(n!) \le n\log_2 n$. So the bound is $\Theta(n \log n)$, and merge sort achieves it. $\blacksquare$

What the bound really counts. $\log_2(n!)$ is the number of bits needed to name one permutation out of $n!$. Each comparison returns one bit. So the theorem is a statement about information: sorting requires learning $\log_2(n!)$ bits, and a yes/no question yields at most one bit, so you need at least that many questions. Framed this way it is the same argument as the source coding bound (T018) with comparisons in place of code symbols, and it explains why the bound is so robust — you are not out-arguing an algorithm, you are out-arguing arithmetic.

For $n = 100$: $\log_2(100!) \approx 525$ comparisons, minimum, ever. Merge sort uses about 573. There is very little room left, and this is why sorting research moved to constant factors, cache behaviour, and adaptivity decades ago.

Where the constant actually sits. Applying Stirling’s approximation to the same quantity sharpens the bound to $n\log_2 n - 1.44n$, and the $-1.44n$ term is what the good implementations are fighting over. Merge sort spends about $n\log_2 n - n$, quicksort about $1.39n\log_2 n$ expected (T007 derives that constant), and the information floor sits below both. That is the entire remaining budget: a constant factor on the leading term and a linear correction. When a new sort is announced, this is the number to check, because the exponent has been settled since 1959.

Forbids

A general-purpose comparison sort in $O(n)$. No arrangement of comparisons gets there, regardless of cleverness, data structures, or engineering effort.

An $O(n \log \log n)$ comparison sort. The bound leaves no room between $n\log n$ and linear either.

Sorting by “just being smarter about pivots.” Quicksort’s worst case is fixable to $O(n\log n)$ by median-of-medians or introsort’s heapsort fallback, but no pivot strategy breaks the floor.

A comparison-based priority queue with both $O(1)$ insert and $O(1)$ extract-min. You could sort $n$ items in $O(n)$ with one, which the bound forbids. This is a useful reduction to keep in your pocket: it kills a whole category of data structure proposals without inspecting them. It also explains why Fibonacci heaps give you $O(1)$ amortized insert and decrease-key but pay $O(\log n)$ on extract-min. The costs can be moved around; the total cannot go below the sorting bound, because the sequence of extract-mins is a sort.

An $O(n)$ algorithm for building a binary search tree from unsorted input. An in-order traversal of the finished tree is a sorted list, produced in $O(n)$, so a linear construction would sort in linear time. Same for building a sorted array, a skip list, or any structure a linear scan can read in order. This “output is a sort” reduction is the fastest way to sanity-check a claimed data-structure bound, and it disposes of most of them.

Does not forbid

It does not forbid sorting in $O(n)$, and treating “sorting is $n \log n$” as a law of nature is the misreading that matters. Radix sort sorts $n$ integers of $w$ bits in $O(wn/\log n)$ time, which is linear for fixed-width keys, and it is not a loophole or a cheat — it is outside the model, because it never compares two elements. It looks at digits. Counting sort is $O(n + k)$ for keys in a small range. Both are real, both ship in production (LSD radix sort is what fast integer-sorting libraries actually use), and neither contradicts a word of the theorem. The right sentence is “comparison sorting is $\Omega(n \log n)$,” and dropping the first word turns a precise result into folklore that costs people real performance. If your keys are 32-bit integers, you are leaving a large constant on the table by reaching for std::sort out of habit.

It does not forbid beating $n \log n$ on nearly-sorted input. The bound is a worst case over all inputs. Timsort runs in $O(n)$ on already-sorted data and detects existing runs, which is why it is Python’s and Java’s default. Adaptive sorts are measured against the number of inversions, not against $n!$, and there is no conflict: the theorem promises that some input costs $n\log n$, not that yours does.

It does not apply to randomized or average-case claims — but it survives both. Worth stating precisely because people expect randomization to help here and it does not. The average number of comparisons over uniformly random inputs is also $\Omega(n\log n)$, and the expected count for any randomized algorithm is too, since a randomized algorithm is a distribution over decision trees and the leaf-counting argument applies to each. Quicksort’s $O(n\log n)$ expected time is not evading the bound, it is meeting it.

It does not say $n\log n$ is achievable in $n\log n$ time. The bound counts comparisons, and a comparison is not always $O(1)$. Sorting long strings, or records with expensive comparators, has different arithmetic — which is why suffix-array construction and string sorting are their own fields.

It does not mean the bound is exactly achievable. $\lceil \log_2(n!)\rceil$ is the information floor, and for some $n$ no algorithm attains it: the minimum number of comparisons to sort 13 elements is 34, while $\lceil \log_2(13!)\rceil = 33$. Lower bounds are constraints, not predictions, and the gap between “no one can do better than this” and “someone can do this” is real even when it is small.

Boundary

Everything that beats the bound does so by leaving the model, and it is worth seeing that they are all the same move:

  • Look at the keys, not at pairs. Radix and counting sort read the representation. Cost: keys must have a usable digit structure and bounded width. This is by far the most-used escape and the most-overlooked.
  • Exploit existing order. Timsort, smoothsort, and the adaptive family run faster when the input is partially sorted, measured in inversions rather than $n$.
  • Know the distribution. Bucket sort is $O(n)$ expected for uniformly distributed keys. Learned index structures push this further by fitting a model of the key distribution.
  • Change the machine. Parallel sorts change the depth but not the total work; sorting networks like AKS achieve $O(\log n)$ depth with $O(n\log n)$ comparators, so the work bound holds. On a word-RAM, integer sorting is possible in $O(n\log\log n)$ (Han and Thorup get $O(n\sqrt{\log\log n})$ expected), which again is not comparison-based.
  • Sort less. Selection and partial sorting have genuinely lower bounds: finding the median is $\Theta(n)$, and getting the top $k$ costs $O(n + k\log k)$, not $O(n\log n)$. If you do not need a total order, do not buy one — this is the boundary with the best practical return, and nth_element exists for exactly this reason.