Find the least number of comparisons needed to sort five elements and devise an algorithm that sorts these elements using this number of comparisons.
I know that the answer is 8, but how do I devise the algorithm?
Let the elements be A, B, C, D, E.
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).
In all cases, maximum 8 comparisons, but it can be less if we get lucky.
EDIT: Here is a simplification of the above.
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.
(E.g., A vs D, B vs D, C vs D, C vs E as a worst case.)