why can't sort 12 elements in 29 comparisons

Question

The information theoretic lower bound for sorting 12 elements is using 29 comparisons, but actually we can't sort them in less than 30 comparisons. My problem is that why we can't reach the information theoretic lower bound? I am looking for an intuitive explanation answer.

Thanks in advance.

Answer 1

I don't think that intution can help much here. It's true that the number of sortings fits in 29 bits ($12 ! < 2^{29}$), so it's in principle possible to identify a permutation by making at most 29 yes-no questions. But a comparison algorithm imposes a huge restriction: instead of chossing among all the arbitrary yes-no questions ($2^{11}=2048$ questions) we must restrict to pair comparisons ($ 66$ questions).

In the book Data Structures and Algorithm Analysis in C++ (Clifford A. Shaffer) it's stated that the claimed result (30 comparisons are needed to sort 12 elements) was proved by brute-force enumeration:

"A survey of analysis techniques for combinatorial algorithms" Bruce Weide mentions the paper

Wells , M.B., "Applications of a language for computing in combinatorics", Proceedings of IFIP Congress 65, vol. 2, 1965, 497-498.

as the one which proved that.