Is it possible to sort an array of 10 elements with 20 comparisons of two elements?

Question

I think it's not, because there are $10!$ permutations of $10$ elements, and $10! \gt 2^{20}$.

Can anyone point me how to prove it rigorously?

Answer 1

Construct a tree whose interior nodes say which pairwise comparisons are performed: the root node says which two elements are compared first, and then one proceeds to one of its two children depending on the result of that comparison. Each interior node of the tree has exactly two children. Each leaf is labeled with the instructions for swapping items in the list in order based on the results of the preceding comparisons. Any comparison sort can be put into this form, and a comparison sort which does at most 20 comparisons can be put into the form of a tree with depth 20 and therefore only $2^{20}=1048576$ leaves.

For a list with 10 elements there are $10! = 3628800$ possible input lists and therefore, for any given comparison sort, two such lists must arrive at the same leaf, and the sort therefore uses the same sequence of swaps to order the items in both lists. But this must leave at least one of them out of order.

This all assumes that the 20 items in the input list are all distinct. But you can assume that they are because a comparison sort which could work for any list of 20 elements must as a special case work for any list of 20 distinct elements.

It is instructive to consider the case of radix sort, for which this analysis does not apply.

Answer 2

You are right and give the correct reason. Already from this simple aspect it follows that at least $22$ comparisons are needed - whether that is possible is then not quite as simple to decide. The flow of the algorithm (including which entries get swapped and which get compared next) is completely determined by the results of the comparisons. By the pigeon-hole principle, two of the $10!$ possible permutations of $\{1,2,\ldots,10\}$ produce the same of $2^{20}$ possible sequences of comparison results, hence produce the same flow and the same swaps - which cannot sort both.