An answer to this question on Stack Overflow.

Question

This is an interview question. Say you have an array of four ints named A, and also this function:

int check(int x, int y){
   if (x<=y) return 1;
   return 0;
}

Now, you want to create a function that will sort A, and you can use only the function checkfor comparisons. How many calls for check do you need?
(It is ok to return a new array for result).
I found that I can do this in 5 calls. Is it possible to do it with less calls (on worst case)?
This is how I thought of doing it (pseudo code):
int[4] B=new int[4]; /* The idea: put minimum values in even cells and maximum values in odd cells using check. Then swap (if needed) between minimum values and also between maximum values. And finally, swap the second element (max of minimums) and the third element (min of maximums) if needed. */ if (check(A[0],A1)==1){ //A[0]<=A1 B[0]=A[0]; B[2]=A1; } else{ B[0]=A1; B[2]=A[0];
} if (check(A[2],A[3])==1){ //A[2]<=A[3] B1=A[2]; B[3]=A[3]; } else{ B1=A[3]; B[3]=A[2]; } if (check(B[0],B1)==0){ //B[0]>B1 swap(B[0],B1); } if (check(B[2],B[3])==0){ //B[2]>B[3] swap(B[2],B[3]); } if (check(B1,B[2])==0){ // B1>B[2] swap(B1,B[2]); }

Answer

In The Art of Computer Programming, p. 183 (Section 3.5.1), Donald Knuth has the following table of lower and upper bounds on the minimum numbers of comparisons:

The ceil(ln n!) is the "information theoretic" lower bound, whereas B(n) is the maximum number of comparisons in an insertion binary sort. Since the lower and upper bounds are equal for n=4, 5 comparisons are needed.

The information theoretic bound is derived by recognizing that there are n! possible orderings of n unique items. We distinguish these cases by asking S yes-no questions in the form of is X<Y?. These questions form a tree which has at most 2^S tips. We need n!<=2^S; solving for S gives ceil(lg(n!)).

Incidentally, you can use Stirling's approximation to show that this implies that sorting requires O(n log n) time.

The rest of the section goes on to describe a number of approaches to creating these bounds and studying this question, though work is on-going (see, for instance Peczarski (2011)).