Find the least number of comparisons needed to sort five ele

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

Solution

simple method -

Split A, B, C, D, E into just two parts (A, B, C) and (D, E).
It will take 3 comparisons to sort (A,B,C)
and 1 to sort (D, E).

Then keep comparing the heads of the lists,
and peel off the smaller of the pair each time.

It will take at most 4 more comparisons to finish the job.

long answer -

We want to know 10 binary relationships:
A vs (B, C, D, E)
B vs (C, D, E)
C vs (D, E)
D vs (E)

Obviously, if we did 10 comparisons, we\'d know each one.
Just saving two comparisons doesn\'t seem too hard.

Let\'s try a merge sort:
1) with 1 comparison we can sort the subset (A, B).
2) with 1 comparison we can sort the subset (C, D).
with 0 comparisons we can sort the subset (E).

So far total of 2 comparisons.

Then we find the smallest overall, with two more comparisons
using the smallest members of each subset.

(Example: A < B, C < D: compare A vs C and the lesser against E)
Let\'s say C < A.

4 comparisons so far.

Now we have either
1) E < C: E is the smallest, C is the second smallest, and we\'re left with (D) (A, B)
2) C < E: C is the smallest and we\'re left with (A, B) (D) (E)

Case 1 (D) and (A, B):
It will take one or two more comparisons (total of 5 or 6) to sort those 3.
D vs A. If D < A, we\'re done, otherwise we need D vs B.


Case 2 (A, B) (D) (E):
Compare D vs E. (Let\'s say E < D).
Compare E vs A.

6 comparisons so far.
Case 2a) E < A: E is second smallest, we have (A, B) D, which takes one or two more (see case 1).
Case 2b) A < E: A is second smallest, we have (B) (E, D) which also takes one or two more (see case 1).