Is n log n a floor for every sorting algorithm, or only some?

## The claim, stated precisely The result people compress into "you can't sort faster than n log n" is really: **any deterministic algorithm that gathers information about the input only by comparing two keys must, on some input of size n, perform at least log2(n!) = Omega(n log n) comparisons.** Three qualifiers do all the work, and dropping any of them turns a theorem into folklore. **Qualifier 1: "comparison".** The model allows exactly one primitive question: given positions i and j, does key i come before key j? The algorithm may branch on the answer, move elements around freely, and use as much memory as it likes. What it may not do is *inspect* a key — no arithmetic on it, no reading its digits, no using it as an index. **Qualifier 2: "worst case".** The bound is a statement about the hardest input for a given algorithm, not about every input. A comparison sort is perfectly free to finish in O(n) on inputs that are already in order; that costs it nothing against the theorem, because the theorem only insists that *some* input forces log2(n!) comparisons. (A companion result bounds the *average* depth of the tree by log2(n!) as well, so shuffling the input does not rescue you either.) **Qualifier 3: "comparisons", not seconds.** The bound counts comparisons. For a comparison sort that is also a time bound, since each comparison costs at least constant time. But it says nothing about data movement, cache traffic, or constants — which is why two sorts that are both Theta(n log n) can differ by a factor of three in wall-clock time. ## Why the model implies the floor With n distinct keys there are n! possible input orderings, and a correct sort must produce a *different* sequence of moves for each one — otherwise two different inputs would be transformed identically, and at most one of the two results can be sorted. Each comparison yields one of two answers, so after k comparisons the algorithm has seen at most 2^k distinct answer-sequences. To tell apart n! cases you need 2^k >= n!, i.e. k >= log2(n!). Stirling's approximation gives log2(n!) = n log2 n - n log2 e + O(log n), so the floor is Theta(n log n). Notice what the argument never mentions: recursion, memory, pivots, or any particular algorithm. It bounds *every* algorithm in the model at once, including ones nobody has invented yet. That is the point of a lower bound, and it is why "maybe someone will find a cleverer comparison sort" is not an answer. ## How linear-time sorts escape A sort that buckets records by the value of one digit does not ask a yes/no question; it performs a single step that routes an element to one of k destinations, which is worth up to log2(k) bits of information rather than one bit. The decision tree for such an algorithm has branching factor k, not 2, and the counting argument that produced Omega(n log n) simply does not apply. Nothing is broken — the algorithm is outside the model, the way a ruler is outside a proof about what you can construct with compass alone. The escape has a price you should be able to name. Non-comparison sorts need keys they can decompose or index: a bounded universe of values, or a fixed number of digits. Their running time depends on that structure — passes over the data proportional to key width, plus work proportional to the size of the value range — so "linear" means linear *in n with key width held constant*. There is even an information-theoretic echo: to have n distinct keys at all you need roughly log2(n) bits per key, so a sort that must actually read every bit of every key is doing Omega(n log n) *bit* operations. The class-level win comes from counting a wide-key pass as one unit of work, which is honest on real hardware and dishonest as a claim to have beaten the theorem. ## Where the wrong answers come from The two failure modes are mirror images. One candidate says the bound is universal and concludes that linear-time sorting is impossible; they cannot explain the sorts that demonstrably do it. The other says a linear-time sort exists and concludes the bound is a myth or a loose heuristic that good implementations beat; they have not noticed that the two statements are about different models and cannot conflict. The answer an interviewer wants is the boundary itself: *what assumption buys the linear time, and what does that assumption cost you.* It is worth noting that mainstream runtimes have made genuinely different choices inside the comparison class — the default sorts shipped by the Python and C++ standard libraries differ in stability, adaptivity, and worst-case guarantees — and yet all of them land at Theta(n log n) comparisons. The bound is not a target anyone is trying to hit; it is the ceiling of the room they are all standing in.