= Solution
Restrict attention to distinct keys; any <comparison sort> must handle these inputs. A deterministic <comparison sort> can be represented by a binary <decision tree>: an internal node records a comparison and its two possible outcomes, and a leaf records the final ordering of the input positions.
There are $n!$ possible relative orders. Two different orders cannot finish at the same leaf, since the <algorithm> would then output the same ordering of positions for both, making at least one result incorrect. A binary <decision tree> of height $h$ has at most $2^h$ leaves. Hence
$$
2^h\geq n!,\qquad h\geq\lceil\log_2(n!)\rceil.
$$
Using the given bound, or just the last $\lfloor n/2\rfloor$ factors of $n!$, gives
$$
\boxed{h\in\Omega(n\log n).}
$$
This is a worst-case <comparison sorting lower bound>, and <merge sort> achieves the same order. The result concerns <comparison sorting>; a procedure that uses numerical digits or bounded integer values has a different computational model.
Back to article page
