 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, henceThis 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.