 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 needsThe bound is worst-case and specific to algorithms obtaining order information through binary comparisons; it does not apply to every possible representation of keys.