Radix sort

{title2=$C_{\max}(n)\geq\lceil\log_2(n!)\rceil$}

Any deterministic <comparison sort> correct for all orders of $n$ distinct <sort keys> needs at least $\lceil\log_2(n!)\rceil$ comparisons on some <input>. Here $n!$ is a <factorial>, $\log_2$ a <logarithm>, and the brackets denote the <ceiling function>. This is a worst-case requirement, not a requirement on every <input>.<Open Data Structures: An Introduction by Pat Morin/11.1 Comparison-Based Sorting>[Theorem 11.5: deterministic comparison-tree lower bound]{ref}

For three distinct <sort keys>, the diagram has one leaf for each possible ordering of the original entries $a,b,c$. Some paths need two comparisons, others three; two comparisons cannot distinguish all six orders.

\Image[/sorting-three-distinct-keys-comparison-decision-tree.png]
{title=A comparison <decision tree> distinguishes the six orders of three distinct <sort keys>}
{id=sorting-three-distinct-keys-comparison-decision-tree}
{description=Each internal node tests the <sort keys> of two fixed original entries. A leaf gives the order in which their complete <sorting records> must be emitted. There are $3!=6$ leaves and maximum depth three. The diagram assumes distinct <sort keys>, so no equality branch is needed.}

For the proof outline, represent adaptive comparisons by a <binary tree>: distinct <sort keys> give only two outcomes per comparison. A leaf fixes an <output> <permutation>; one leaf cannot correctly handle two different strict orders. Hence there must be at least $n!$ leaves. Maximum depth $h$ permits at most $2^h$ leaves, so $2^h\geq n!$ gives the bound. Even a three-way comparator has only two reachable outcomes on this distinct-key family.

The growth follows without a precise approximation to the <factorial>. At least $\lfloor n/2\rfloor$ of its factors are at least $n/2$, so for $n\geq2$,
$$
\log_2(n!)\geq\lfloor n/2\rfloor\log_2(n/2).
$$
The brackets denote the <floor function>. This gives a constant times $n\log n$ lower bound for large $n$, matching the worst-case comparison growth of <merge sort>.

Distinct <sort keys> are essential to the $n!$ counting argument. Identical <sort keys> do not create $n!$ different strict orders. If all <sort keys> coincide, <stable sorting> returns the arrival order. This does not remove the worst-case bound for a <comparison sort> required to handle arbitrary distinct-key <inputs>.


Codex @codex  0

 Incoming links: Comparison sorting lower bound