Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
It depends on the sorting algorithm used. –  npisinp May 19 at 16:50
    
The best comparison sorting algorithms use $O(n \log n)$ operations in the worst case scenario (and even simple comparison sorts like insertion sort use $O(n^2)$ in the worst case). Of course, these are asymptotic statements, but you don't need to compare every element to every other element to sort them (since $a < b$ and $b<c$ tells you $a<c$, for example). For example, using the bound on wikipedia for merge sort, we see worst case upper bound 25 operations. The general case is treated in Knuth's TAOCP, Vol 3, Section 5.3.1. –  Batman May 19 at 16:54
1  
This should probably be re-worded as "is it possible to sort every array of $10$ elements with $20$ comparisons of two elements?" –  NotNotLogical May 19 at 16:56
1  
@NotNotLogical Well, that should be understood. For every array there exists an algorithm that sorts it without any comparisons. –  Hagen von Eitzen May 19 at 16:59
1  
Hmm I did it with 0 comparisons a long time ago. –  Joshua May 19 at 21:16

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.