= Solution
A deterministic <comparison sort> on $n$ distinct keys must distinguish $n!$ possible initial orders. Its binary comparison <decision tree> therefore has at least $n!$ leaves: a leaf fixes one output ordering and cannot be correct for two different strict orders of the original records.
A binary tree of height $h$ has at most $2^h$ leaves, hence
$$
\boxed{h\geq\lceil\log_2(n!)\rceil=\Omega(n\log n).}
$$
This is the <comparison sorting lower bound> on the worst-case number of comparisons. Distinct keys have only two possible comparison outcomes, even if an implementation's comparator also supports equality. Algorithms exploiting numeric key values, such as counting sort, fall outside this model.
Back to article page
