Least number of comparisons needed to sort (order) 5 elements

Problem Detail: 

Find the least number of comparisons needed to sort (order) five elements and devise an algorithm that sorts these elements using this number of comparisons.

Solution: There are 5! = 120 possible outcomes. Therefore a binary tree for the sorting procedure will have at least 7 levels. Indeed, $2^h$ ≥ 120 implies $h $ ≥ 7. But 7 comparisons is not enough. The least number of comparisons needed to sort (order) five elements is 8.

Here is my actual question: I did find an algorithm that does it in 8 comparison but how can I prove that it can't be done in 7 comparisons?

Asked By : atulgangwar

Answered By : Raphael

The solution is wrong. Demuth [1; via 2, sec. 5.3.1] shows that five values can be sorted using only seven comparisons, i.e. that the "information theoretic" lower bound is tight in this instance.

The answer is a method tailored to $n=5$, not a general algorithm. It's also not very nice. This is the outline:

1. Sort the first two pairs.

2. Order the pairs w.r.t. their respective larger element.

   Call the result $[a,b,c,d,e]$; we know $a<b<d$ and $c<d$.

3. Insert $e$ into $[a,b,d]$.

4. Insert $c$ into the result of step 3.

The first step clearly takes two comparisons, the second only one. The last two steps take two comparisons each; we insert into a three-element list in both cases (for step 4., note that we know from $c<d$ that $c$ is smaller than the last element of the list at hand) and compare with the middle element first. That makes a total of seven comparisons.

Since I don't see how to write "nice" pseudocode of this, see here for a tested (and hopefully readable) implementation.

---

1. Ph.D. thesis (Stanford University) by H.B. Demuth (1956)

   See also Electronic Data Sorting by H.B. Demuth (1985)

2. Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44981