Does a three-way comparator break the n log n sorting lower bound?

## The question behind the question An interviewer who has just heard you prove the Omega(n log n) bound often probes it by loosening one assumption: suppose a single call told you "less", "equal", or "greater" — does the argument survive? It is a good probe because it separates people who understand the proof's machinery from people who memorised its conclusion. The answer requires knowing exactly which step of the derivation used the number two. ## Where the two entered, and what replaces it The derivation had one step that depended on comparisons being binary: *a tree of height h with branching factor 2 has at most 2^h leaves.* Everything else — that correctness forces a distinct leaf per input ordering, that there are n! orderings, that the tree's height is the worst-case step count — is untouched by the comparator's arity. So replace that step. With three outcomes per node the tree has branching factor 3 and at most 3^h leaves, giving: ``` 3^h >= n! h >= log3(n!) = log2(n!) / log2(3) ``` Since log2(3) is about 1.585, the new floor is roughly 0.63 times the old one — you might hope to shave about 37% off the comparison count. But `log3(n!)` and `log2(n!)` differ by a constant multiplier, and constant multipliers are exactly what asymptotic notation discards. Both are `Theta(n log n)`. The class is untouched. This generalises usefully. A primitive with k outcomes yields a floor of `log_k(n!) = log2(n!) / log2(k)`, so each step is worth `log2(k)` bits instead of one bit. To leave `Theta(n log n)` you would need k to *grow with n* — and that is precisely what a non-comparison sort does when it routes an element into one of many buckets by digit value. Seen this way, three-way comparison and radix bucketing are the same lever pulled to different degrees: the first pulls it a constant amount and gains a constant factor; the second pulls it far enough to change the class, at the price of needing keys it can decompose. ## The sharper answer: for distinct keys you gain nothing at all There is a subtlety worth raising unprompted, because it shows you thought past the algebra. The counting argument assumed n *distinct* keys — that is where n! came from. But if all keys are distinct, no comparison ever returns "equal". The equal-branch subtrees are unreachable, the algorithm's live decision tree is binary again, and the true floor stays at `log2(n!)`. The `log3(n!)` figure is still a valid lower bound in the sense that it is not violated, but it is a *weaker* bound — it is below the truth and therefore useless. Concretely: five distinct keys still need at least 7 comparisons in the worst case, whatever the comparator returns, because `log2(120) = 6.907`. The ternary bound would suggest `log3(120) = 4.3`, i.e. 5 comparisons, and no algorithm achieves that on distinct input. A lower bound being unattainable is not a contradiction; it just means you proved something weaker than you could have. The three-outcome bound becomes the honest one only when the input may contain duplicates. Then there are genuinely fewer distinguishable outcomes to separate (a multiset with repeats has fewer distinct arrangements than n!), the "equal" branch carries real information, and an algorithm can exploit it. That is the actual reason three-way comparison earns its place in practice: three-way partitioning collapses runs of equal keys into a middle region that never needs sorting again, turning duplicate-heavy input from a worst case into a best case. The win is on the input distribution, not on the theorem. ## How to answer this out loud The strong answer has four beats: name the exact step of the proof that used the branching factor; redo it with three; observe that a change of logarithm base is a constant factor and therefore invisible to the complexity class; then add that with distinct keys the third outcome is unreachable, so even the constant-factor relief is illusory and the practical benefit lies elsewhere. The weak answer is "three outcomes means one and a half times more information, so it is faster" — plausible-sounding, silent on whether the class changes, and unable to say when the extra outcome is ever reachable. ## The general lesson Lower-bound arguments are robust to cosmetic changes in the model and fragile to structural ones. Adding outcomes to a primitive, allowing unlimited memory, permitting randomization, or letting the algorithm see comparisons it made earlier for free — none of these move `Theta(n log n)`. What moves it is changing what a step can *learn*: an operation whose number of outcomes scales with the data leaves the comparison model entirely. Knowing which perturbations matter is the difference between reciting a theorem and being able to use one.