THE COMPARISON BOUND — a dart

THE COMPARISON BOUND why no comparison sort beats n log n — counting the outcomes

There is a floor under comparison sorting that no cleverness can break: Ω(n log n) comparisons. The proof is a counting argument — a sort must distinguish all n! possible orderings of the input, and each yes/no comparison splits the possibilities in at most two, so you need at least log₂(n!) comparisons to tell them apart (a decision tree of n! leaves has depth ≥ log₂(n!)). For n=4 there are 24 orderings, and since 2⁴=16 < 24 ≤ 32=2⁵, you need at least 5 comparisons. It is an information-theoretic limit — and it is why radix sort (which does not compare) can go faster.

THE TECHNIQUE ≥ log₂(n!) comparisons — a decision tree of n! leaves

The demo computes the bound for n=4: 4!=24 orderings need ≥ log₂(24) = 5 comparisons: live demo

HISTORY & CREDIT comparison sort lower bound · decision tree

“A smarter comparison sort could beat n log n.” — no: distinguishing n! orderings needs log₂(n!) comparisons; it is a proven floor. cited

the outcomes · a sort must tell apart all n! input orderings.
the tree · each comparison branches two ways — depth ≥ log₂(n!) to reach n! leaves.
the bound · log₂(n!) = Θ(n log n) — the information-theoretic floor for comparison sorts.

A limit proven by counting orderings, not by trying algorithms — the floor comparison sorts cannot cross. theorem

RECOMMEND FOR I-13 the outcome count, on the compiler

On the canonical compiler, 4! = 24 and the smallest c with 2ᶜ ≥ 24 is 5 — so at least 5 comparisons:

$ i13 run or_comparisonbound.i13 # min c with 2^c >= n! RUN OK · 146 step(s) · peak stack 5 · call depth 6 nfact = 24 -- 4! min_comparisons = 5 -- 2^4=16 < 24 <= 32=2^5 is5 = 1

Recommend as a NULL — a theorem, cleanly. The comparison lower bound is an information-theoretic theorem (B39): every correct comparison sort obeys it by counting. i13 grounds the count (24 orderings need 5 comparisons). Not a mechanism a keeper enacts. NULL — the floor that explains why radix sort (dart 506) can go faster by not comparing.