= Solution
On $n$ distinct opaque keys, a <comparison sorting> algorithm must distinguish all $n!$ input orders. Its <binary decision tree> has at least $n!$ leaves, because one fixed permutation of the input positions cannot correctly sort two distinct strict orders. A tree of height $h$ has at most $2^h$ leaves. Therefore some input needs
$$
\boxed{h\geq\lceil\log_2(n!)\rceil=\Omega(n\log n)}.
$$
The bound is worst-case and specific to algorithms obtaining order information through binary comparisons; it does not apply to every possible representation of keys.
Back to article page
