Question

(§3.4 # 3) Use the previous problem to show that the average number of binary
comparisons required to sort n items is at least O(n log2 n).

Answer 1

The sorting algorithm must output a permutation of the input . The key to the argument is that

(a) there are n! different possible permutations the algorithm might output, and

(b) for each of these permutations, there exists an input for which that permutation is the only correct answer.

In fact, if we fix a set of n distinct elements, then there will be a 1-1 correspondence between the different orderings the elements might be in and the permutations needed to sort them.

Given (a) and (b) above, we can fix some set of inputs (e.g., all orderings of {1, 2,... ,n}), one for each of the output permutations. Let S be the set of these inputs that are consistent with the answers to all comparisons made so far so, initially, . We can think of a new comparison as splitting S into two groups: those inputs for which the answer would be YES and those for which the answer would be NO.

Now, suppose an adversary always gives the answer to each comparison corresponding to the larger group. Then, each comparison will cut down the size of S by at most a factor of 2. Since S initially has size , and by construction, the algorithm at the end must have reduced down to 1 in order to know which output to produce, the algorithm must make at least comparisons before it can halt.

We can then solve =

​​​​​​​