Twenty Nine Comparisons

A comparison sort is a decision tree: each internal node is one comparison with two outcomes, and each leaf is one possible output permutation. For n=12n = 12 distinct elements, what is the smallest number of comparisons that some input is guaranteed to force, for any comparison sort?

Useful values: 12!=47900160012! = 479001600, 228=2684354562^{28} = 268435456, 229=5368709122^{29} = 536870912, log⁡212≈3.585\log_2 12 \approx 3.585.

A

12

B

29

C

43

D

66