Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 6 / b / 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. HenceUsing the given bound, or just the last $\lfloor n/2\rfloor$ factors of $n!$, givesThis 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.