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

<p><a href="https://i.stack.imgur.com/Nt2Rj.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Nt2Rj.png" alt="Donald Knuth, TAOCP, p. 183, Section 3.5.1"></a></p>

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

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

<p>Incidentally, you can use <a href="https://en.wikipedia.org/wiki/Stirling&#39;s_approximation" rel="nofollow noreferrer">Stirling's approximation</a> to show that this implies that sorting requires <code>O(n log n)</code> time.</p>

<p>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 <a href="https://arxiv.org/abs/1108.0866" rel="nofollow noreferrer">Peczarski (2011)</a>).</p>
Sorting 4 numbers with minimum x<y comparisons
<p>This is an interview question. Say you have an array of four ints named A, and also this function:</p>

<pre><code>int check(int x, int y){
   if (x&lt;=y) return 1;
   return 0;
}
</code></pre>

<p>Now, you want to create a function that will sort A, and you can use only the function <code>check</code>for comparisons. How many calls for <code>check</code> do you need?<br>
(It is ok to return a new array for result).           </p>

<p>I found that I can do this in 5 calls. Is it possible to do it with less calls (on worst case)?                 </p>

<p>This is how I thought of doing it (pseudo code):                     </p>

<pre><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],A[1])==1){ //A[0]&lt;=A[1]
    B[0]=A[0];
    B[2]=A[1];
}
else{
    B[0]=A[1];
    B[2]=A[0];  
}
if (check(A[2],A[3])==1){ //A[2]&lt;=A[3]
    B[1]=A[2];
    B[3]=A[3];
}
else{
    B[1]=A[3];
    B[3]=A[2]; 
}
if (check(B[0],B[1])==0){ //B[0]&gt;B[1]
    swap(B[0],B[1]);
}
if (check(B[2],B[3])==0){ //B[2]&gt;B[3]
    swap(B[2],B[3]);
}
if (check(B[1],B[2])==0){ // B[1]&gt;B[2]
    swap(B[1],B[2]);
}
</code></pre>