Does the Omega(n log n) comparison-sort lower bound mean no sort can ever run faster?
answer
- ask what the bound quantifies over
- which operation is being counted?
- one comparison answer is one bit
- keys can be read, not only compared
- bucketing by value never compares
basics
~20 sThe bound binds a model, not the task. It covers only algorithms that learn order by comparing pairs of keys. Sorts that use a key's value directly as a position escape it and run in linear time.
solid answer
~50 sNo — the bound is about the comparison model, not about sorting as a task. It says any algorithm whose only way of learning order is asking "does a come before b?" must, on some input of size n, make Ω(n log n) such comparisons. The argument is a counting one: a comparison answer is worth one bit, there are n! orderings to tell apart, and that needs about n log n bits. A key-indexed sort never plays that game — it reads a key's value and uses it directly as a position, resolving far more than one bit per step. That is why tallying packet-log records by port number, where every key lies in a small fixed range, sorts them in linear time. It buys that with conditions: bounded key range, and memory proportional to it.
go deeper
Be ready to state that the n log n floor covers sorts that only compare keys, and that it does not forbid every fast sort. Naming one key-indexed approach in a sentence is enough at this level.
Explain why a single comparison yields one bit and why separating every possible ordering forces the log factor. Then say precisely which assumption a key-indexed sort declines to make.
Show when the escape hatch is real in production: bounded key ranges, memory for the tally, and the crossover point where the range dwarfs the input and the linear-time sort becomes the slower choice.
Own the framing that bounds are relative to a model. Decide when it is worth constraining an input contract — fixing a key range at the boundary, for instance — to unlock an algorithm class the general case cannot use.
## What a lower bound on a problem claims "Comparison sorting is Ω(n log n)" is not a statement about any particular algorithm. It quantifies over *every* algorithm that could ever be written inside a stated model of computation: however clever, in the worst case it needs at least on the order of n log n operations of the counted kind. That is far stronger, and far rarer, than "this algorithm runs in O(n log n)", which describes one program's ceiling. The first is a floor under a **problem**; the second is a ceiling over an **algorithm**. Two words in the claim carry all the weight, and candidates routinely drop both: *worst case*, and *comparison*. ## The model the bound actually binds In the comparison model, an algorithm receives n keys, may move them around freely, and may learn about their relative order **only** by asking "is a before b?" for two keys and reading the answer. It may never inspect a key's internal value. Why a floor exists there: consider a fixed set of n distinct keys presented in each of its n! possible arrangements. Sorted output requires a different permutation of moves for each arrangement, so the algorithm must behave differently in all n! cases. But everything it does is determined by the sequence of comparison answers it received. A yes/no answer has two outcomes, so an algorithm that never makes more than C comparisons has at most 2^C distinguishable executions. Correctness forces 2^C >= n!, so C >= log2(n!), and standard bounds on log2(n!) place that in Ω(n log n). The version to say out loud in an interview: one comparison buys one bit, there are n! orderings to separate, and separating n! things costs about n log n bits. ## What the bound does not say - **It does not say every sort takes n log n time.** It is a floor on comparisons *in the worst case*. An adaptive sort can finish a nearly-ordered input in linear time without contradicting anything — the bound only promises that *some* input forces n log n. - **It does not promise n log n is reachable.** That is a separate, upper-bound fact, proved by exhibiting algorithms that reach it. A matching upper and lower bound is what "optimal" means. - **It says nothing about algorithms outside the model.** A bound is always relative to what you allow the algorithm to do. ## Leaving the model on purpose Key-indexed methods break the model's central assumption. Reading a 16-bit key and using it as an index resolves 65,536 possibilities in a single step, not one bit. Nothing is ever compared, so the counting argument simply does not apply — no theorem is being violated. A concrete shape: ten million packet-log records keyed by port number, every key inside the fixed range 0 to 65535. Allocate a tally across the range, make one pass over the records incrementing counters, then sweep the range emitting keys in order. Cost is proportional to n plus the range size, which at these numbers is linear in n. Now flip the numbers — five hundred records keyed by a 64-bit identifier — and the range term is astronomically larger than the data. The escape hatch is real and conditional, never free: it demands a bounded key space, memory proportional to it, and a direct key-to-index mapping. ## Why general-purpose sorts stay comparison sorts A general-purpose sort must accept an arbitrary ordering rule supplied by its caller and can assume nothing about the internal structure of keys. Inside that contract, comparison is the only available primitive and the bound applies in full. That is why the default sorts shipped with mainstream platforms are comparison-based hybrids — a stable adaptive merge-and-insertion hybrid in the Timsort family, or an introsort-style quicksort with a heapsort fallback — while key-indexed sorts appear as specialist tools invoked when the data's shape is known. ## The floor that never lifts Even outside the comparison model, sorting is Ω(n): the output depends on every key, so an algorithm that never reads one can be defeated by changing it. Linear time is the best anyone can hope for on unsorted input, in any model. The comparison bound tells you which class you have signed up for; the input-reading bound tells you where the universal floor is. ## Interview register The wrong answer this question hunts for is "n log n is proven, so linear-time sorting is impossible." The right answer names the assumption the proof rests on, names the family of algorithms that decline that assumption, and states honestly what they demand in return.
- What has to be true about the keys before a linear-time key-indexed sort is worth reaching for?Keys must map directly to indices in a bounded range, and you must be willing to spend memory proportional to that range. Cost is O(n + k) for a range of size k, so it wins only while k is comparable to or smaller than n. With sparse or very wide keys — long identifiers, arbitrary text, floating-point values — the range term dominates and a comparison sort is both faster and far less memory-hungry.
- A teammate says nobody has found a faster comparison sort, so n log n must be the limit. Is that reasoning sound?The conclusion is right but the reasoning is not. "Nobody has found one" is absence of evidence and would be equally true of a problem someone cracks next year. Here we have something much stronger: a proof that counts orderings and shows no such algorithm can exist in the model. Always ask whether a claimed limit rests on a proof or on a failed search — they justify very different engineering decisions.
- Does the bound forbid a comparison sort from finishing a particular input in linear time?No. The bound is a worst-case statement: it guarantees that for every comparison sort there exists an input forcing Ω(n log n) comparisons. It says nothing about other inputs. Adaptive sorts exploit exactly this — an already-ordered or nearly-ordered sequence can be confirmed with a single linear scan of comparisons, which is why production sorts detect existing runs before doing any real work.
Twenty yes/no questions can single out one item from at most about a million. Asking "what is your key's value?" is not a yes/no question, so it is not covered by the twenty-questions arithmetic at all.
saying these in an interview costs you the question
- Claims no sorting algorithm can ever beat n log n
- Says linear-time sorts violate a proven theorem
- Treats the bound as a limit on all work, not comparisons
- Assumes key-indexed sorts need no conditions on keys
- Confuses one algorithm's ceiling with the problem's floor