Least number of comparisons needed to sort (order) 5 elements
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:


Sort the first two pairs.
Order the pairs w.r.t. their respective larger element.

Call the result $[a,b,c,d,e]$; we know $a&lt;b&lt;d$ and $c&lt;d$.
Insert $e$ into $[a,b,d]$.
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&lt;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.




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

See also Electronic Data Sorting by H.B. Demuth (1985)
Sorting and Searching
by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)