Design an efficient algorithm to sort 5 distinct keys in fewer than 8 comparisons

Question

Design an efficient algorithm to sort 5 distinct - very large - keys less than 8 comparisons in the worst case. You can't use radix sort.

Answer 1

Five item can be sorted with seven comparisons in the worst cast because log₂(5!) = 6.9. I suggest to check if any standard sort sort algorithm achieves this number - if not it should be quite easy to hard-code a comparison sequence because of the low number of required comparisons.

I suggest to write a program to find the comparison sequence. Create a list with all 120 permutations of the numbers one to five. Then try all ten possible comparisons and select that one, that splits the list as good as possible in two equal sized lists. Perform this split and apply the same procedure to two lists recursively.

I wrote a small program to do this and here is the result.

Comparison 1: 0-1 [60|60] // First comparison item 0 with item 1, splits case 60/60
Comparison 2: 2-3 [30|30] // Second comparison for the first half of the first comparison
Comparison 3: 0-2 [15|15] // Third comparison for the first half of the second comparison for the first half of first comparison
Comparison 4: 2-4 [8|7]
Comparison 5: 3-4 [4|4]
Comparison 6: 1-3 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 6: 1-4 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 5: 0-4 [4|3]
Comparison 6: 1-2 [2|2]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 6: 1-2 [1|2]
Comparison 7: 1-3 [1|1]
Comparison 4: 0-4 [8|7]
Comparison 5: 1-4 [4|4]
Comparison 6: 1-3 [2|2]
Comparison 7: 3-4 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 6: 3-4 [2|2]
Comparison 7: 0-3 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 5: 0-3 [4|3]
Comparison 6: 1-3 [2|2]
Comparison 7: 2-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 6: 2-4 [2|1]
Comparison 7: 3-4 [1|1]
Comparison 3: 0-3 [15|15] // Third comparison for the second half of the second comparison for the first half of first comparison
Comparison 4: 3-4 [8|7]
Comparison 5: 2-4 [4|4]
Comparison 6: 1-2 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 6: 1-4 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 5: 0-4 [4|3]
Comparison 6: 1-3 [2|2]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 6: 1-2 [2|1]
Comparison 7: 1-3 [1|1]
Comparison 4: 0-4 [8|7]
Comparison 5: 1-4 [4|4]
Comparison 6: 1-2 [2|2]
Comparison 7: 2-4 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 6: 2-4 [2|2]
Comparison 7: 0-2 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 5: 0-2 [4|3]
Comparison 6: 1-2 [2|2]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 6: 2-4 [1|2]
Comparison 7: 3-4 [1|1]
Comparison 2: 2-3 [30|30] // Second comparison for the second half of the first comparison
Comparison 3: 0-3 [15|15]
Comparison 4: 0-4 [7|8]
Comparison 5: 0-2 [3|4]
Comparison 6: 2-4 [2|1]
Comparison 7: 3-4 [1|1]
Comparison 6: 1-2 [2|2]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 5: 1-4 [4|4]
Comparison 6: 2-4 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 6: 1-2 [2|2]
Comparison 7: 0-2 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 4: 3-4 [7|8]
Comparison 5: 0-4 [3|4]
Comparison 6: 1-2 [1|2]
Comparison 7: 1-3 [1|1]
Comparison 6: 1-3 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 5: 2-4 [4|4]
Comparison 6: 1-4 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 6: 1-2 [2|2]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 3: 0-2 [15|15]
Comparison 4: 0-4 [7|8]
Comparison 5: 0-3 [3|4]
Comparison 6: 2-4 [1|2]
Comparison 7: 3-4 [1|1]
Comparison 6: 1-3 [2|2]
Comparison 7: 2-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 5: 1-4 [4|4]
Comparison 6: 3-4 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 6: 1-3 [2|2]
Comparison 7: 0-3 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 4: 2-4 [7|8]
Comparison 5: 0-4 [3|4]
Comparison 6: 1-2 [2|1]
Comparison 7: 1-3 [1|1]
Comparison 6: 1-2 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 5: 3-4 [4|4]
Comparison 6: 1-4 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 6: 1-3 [2|2]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]

But now the question is how to implement this in an efficient way. Maybe one could use a look-up table to store the comparison sequence. I am also not sure how to derive the ordered output from this comparison sequence in an efficient way.

Sorting the result from above by the comparison reveals an obvious structure for the first comparisons, but it becomes harder with increasing comparison number. All blocks are symmetric around the middle indicated by -----.

Comparison 1: 0-1 [60|60]

Comparison 2: 2-3 [30|30]
Comparison 2: 2-3 [30|30]

Comparison 3: 0-2 [15|15]
Comparison 3: 0-3 [15|15]
-----
Comparison 3: 0-3 [15|15]
Comparison 3: 0-2 [15|15]

Comparison 4: 2-4 [8|7]
Comparison 4: 0-4 [8|7]
Comparison 4: 3-4 [8|7]
Comparison 4: 0-4 [8|7]
-----
Comparison 4: 0-4 [7|8]
Comparison 4: 3-4 [7|8]
Comparison 4: 0-4 [7|8]
Comparison 4: 2-4 [7|8]

Comparison 5: 3-4 [4|4]
Comparison 5: 0-4 [4|3]
Comparison 5: 1-4 [4|4]
Comparison 5: 0-3 [4|3]
Comparison 5: 2-4 [4|4]
Comparison 5: 0-4 [4|3]
Comparison 5: 1-4 [4|4]
Comparison 5: 0-2 [4|3]
-----
Comparison 5: 0-2 [3|4]
Comparison 5: 1-4 [4|4]
Comparison 5: 0-4 [3|4]
Comparison 5: 2-4 [4|4]
Comparison 5: 0-3 [3|4]
Comparison 5: 1-4 [4|4]
Comparison 5: 0-4 [3|4]
Comparison 5: 3-4 [4|4]

Comparison 6: 1-3 [2|2]
Comparison 6: 1-4 [2|2]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-2 [1|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 3-4 [2|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 2-4 [2|1]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-4 [2|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 1-2 [2|1]
Comparison 6: 1-2 [2|2]
Comparison 6: 2-4 [2|2]
Comparison 6: 1-2 [2|2]
Comparison 6: 2-4 [1|2]
-----
Comparison 6: 2-4 [2|1]
Comparison 6: 1-2 [2|2]
Comparison 6: 2-4 [2|2]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-2 [1|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-4 [2|2]
Comparison 6: 2-4 [1|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 3-4 [2|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 1-2 [2|1]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-4 [2|2]
Comparison 6: 1-3 [2|2]

Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
-----
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]

Answer 2

Sample sequence of operations, using mergesort (the merge function below will merge two sorted sublists into a single sorted combined list):

elements[1..2] <- merge(elements[1..1], elements[2..2]) # 1 comparison
elements[3..4] <- merge(elements[3..3], elements[4..4]) # 1 comparison
elements[3..5] <- merge(elements[3..4], elements[5..5]) # 1-2 comparisons
elements[1..5] <- merge(elements[1..2], elements[3..5]) # 2-4 comparisons

Answer 3

It has to be 7 or more comparisons.

There are 120 (5 factorial) ways for 5 objects to be arranged. An algorithm using 6 comparisons can only tell apart 2^6 = 64 different initial arrangements, so algorithms using 6 or less comparisons cannot sort all possible inputs.

There may be a way to sort using only 7 comparisons. If you only want to sort 5 elements, such an algorithm could be found (or proved not to exist) by brute force.

Answer 4

Compare A to B and C to D. WLOG, suppose A>B and C>D. Compare A to C. WLOG, suppose A>C. Sort E into A-C-D. This can be done with two comparisons. Sort B into {E,C,D}. This can be done with two comparisons, for a total of seven.

Answer 5

This is pseudocode based on Beta's answer. Might have some mistakes as I did this in a hurry.

if (A > B)
    swap A, B
if (C > D)
    swap C, D
if (A > C)
    swap A, C

if (E > C)
    if (E > D) %A C D E
        if (B > D)
            if (B > E)
                return (A, C, D, E, B)
            else
                return (A, C, D, B, E)
         else
            if (B < C)
                return (A, B, C, D, E)
            else
                return (A, C, B, D, E)

    else %A C E D
        if (B > E)
            if (B > D)
                return (A, C, E, D, B)
            else
                return (A, C, E, B, D)
         else
            if (B < C)
                return (A, B, C, E, D)
            else
                return (A, C, B, E, D)
else
    if (E < A) % E A C D
        if (B > C)
            if (B > D)
                return (E, A, C, D, B)
            else
                return (E, A, C, B, D)
         else
             return (E, A, B, C, D)

    else %A E C D
        if (B > C)
            if (B > D)
                return (A, E, C, D, B)
            else
                return (A, E, C, B, D)
         else
            if (B < E)
                return (A, B, E, C, D)
            else
                return (A, E, B, C, D)

Answer 6

According to Wikipedia:

Determining the exact number of comparisons needed to sort a given number of entries is a computationally hard problem even for small n, and no simple formula for the solution is known."

Presumably this means there is no known tractable (efficient) algorithm for determining an exactly optimal comparison sort.

Answer 7

A B C D E

A
| C D E     - 1 Comparison
B

A C
| | E       - 1 Comparison
B D

  A
 / \
B   C   E   - 1 Comparison
     \
      D

E needs 3 comparisons. It should be compared to A, C, D

Try A-C-D-E in that order.

Overall there will be nine comparisons -- not very performant.

Answer 8

Others have stated that there are 5! = 120 arrangements (permutations) to handle, so you need 7 comparisons. To identify the permutation, in principle, you can construct a big nested if statement 7 comparisons deep. Having identified the permutation, a precalculated swap/rotation sequence can be applied.

The first problem is that the choice of second comparison depends on the result of the first comparison and so on. The trick at each stage is to choose a good comparison to divide the current set of possible permutations into two equal subsets. Simplest approach - evaluate the split that each comparison would achieve until you find a suitably balanced one. Exit early if you find a perfect balance, but be aware that perfect balance won't always be possible as we don't have exactly 2^7=128 permutations - in some (I assume 8) cases, we only need six comparisons.

The second problem is designing the swap/rotation sequences for each of the 120 possible permutations, and that's probably a dynamic programming thing. Probably requires recursive search of an if-I-do-this, the next result is that, then recurse "game tree", and you should really cache intermediate results IOW. Too tired to figure out the details ATM, sorry.

You might put all the steps into a digraph that fans out (identifying the permutation), then fans back in (applying each reordering step). Then, probably run it through a digraph minimisation algorithm.

Wrap this up in a code generator and you're done - your own algorithmically near-perfect 5 item sorter. The digraph stuff kind of implies gotos in the generated code (esp. if you minimise), but people tend to turn a blind eye to that in generated code.

Of course all this is a bit brute force, but why bother with elegance and efficiency - odds are you'll only run the working generator once anyway, and the problem size is small enough to be achievable (though probably not if you do independent naive "game tree" searches for each permutation).

Answer 9

Sorting networks have a restricted structure, so don't answer the original question; but they're fun.
List of Sorting Networks generates nice diagrams or lists of SWAPs for up to 32 inputs. For 5, it gives

There are 9 comparators in this network, grouped into 6 parallel operations.  
[[0,1],[3,4]]  
[[2,4]]  
[[2,3],[1,4]]  
[[0,3]]  
[[0,2],[1,3]]  
[[1,2]]

Answer 10

did someone implemented the above algorithm? it is a bit hard