1.Previous
3.Next

most easily seen using concepts from information theory. The Shannon entropy of such a random permutation is bits. Since a comparison can give only two results, the maximum amount of information it provides is 1 bit. Therefore, after k comparisons the remaining entropy of the permutation, given the results of those comparisons, is at least bits on average. To perform the sort, complete information is needed, so the remaining entropy must be 0. It follows that

1.Previous
3.Next