Sort array of 5 integers with a max of 7 compares

Question

How can I sort a list of 5 integers such that in the worst case it takes 7 compares? I don't care about how many other operations are performed. I don't know anything particular about the integers.

I've tried a few different divide and conquer approaches which get me down to 8 compares, such as following a mergesort approach, or combining mergesort with using binary search to find the insertion position, but every time I end up with 8 compares worst case.

Right now I'm just looking for a hint, not a solution.

Answer 1

There is only one way to start this process (and for nearly all of your decisions of what to compare in later steps, there is only one correct one). Here's how to figure it out. First, note that there are $2^7 =128$ possible answers you can get for your comparisons, and $5! = 120$ different permutations you need to distinguish between.

The first comparison is easy: you have to compare two keys, and since you don't know anything about them, all choices are equally good. So let's say you compare $a$ and $b$, and find that $a \leq b$. You now have $2^6 = 64$ possible answers left, and $60$ possible permutations remaining (since we have eliminated half of them).

Next, we can either compare $c$ and $d$, or we can compare $c$ to one of the keys we used in the first comparison. If we compare $c$ and $d$, and learn that $c \leq d$, then we have $32$ remaining answers and $30$ possible permutations. On the other hand, if we compare $c$ with $a$, and we discover that $a \leq c$, we have $40$ possible permutations remaining, because we have eliminated $1/3$ of the possible permutations (those with $c \leq a \leq b$). We only have $32$ possible remaining answers, so we're out of luck.

So now we know that we have to compare the first and second keys, and the third and fourth keys. We can assume that we have $a\leq b$ and $c \leq d$. If we compare $e$ to any of these four keys, by the same argument we used in the previous step, we might only eliminate $1/3$ of the permutations remaining, and we're out of luck. So we have to compare two of the keys $a,b,c,d$. Taking into account symmetry, we have two choices, compare $a$ and $c$ or compare $a$ and $d$. A similar counting argument shows we must compare $a$ and $c$. We can assume without loss of generality that $a \leq c$, and now we have $a \leq b$ and $a \leq c \leq d$.

Since you asked for a hint, I won't go through the rest of the argument. You have four comparisons left. Use them wisely.

Answer 2

You can find this in The Art of Computer Programming vol III, by D.Knuth, but the strategy is as this (I'll assume you have array $\{a,b,c,d,e\}$): If you want hint read just first two lines of my answer

• First group pairs of numbers: $(a,b), (c,d)$.
• Compare pairs to sort them e.g: $a<b, c<d$.
• Compare smallest elements of pairs, we get result e.g $a<c$.
• Compare the last element $e$, with bigger element in last comparison ($c$)
  • If $e<c$, is easy to end up with 3 remaining comparison. Finished.
  • If $e>c$ then you should sort $\{b,c,d,e\}$ with knowledge $c<e, c<d$.
    • $Compare(d,e)$, if $d < e$ then
      • $Compare(b,d)$, if $b>d$
        • $Compare(b,e)$. Finished.
      • if $b<d$
        • $Compare(b,c)$. Finished.
    • if $d > e$
      • $Compare(b,e)$ if $b>e$
        • $Compare(b,d)$. Finished.
      • if $b<e$
        • $Compare(b,c)$. Finished.

All above mentioned ways are cause to at most three comparison after first comparison of $e$ with $c$. (means 7 at most).

Answer 3

A solution implementation in Python:

def sort_five_elements(arr):
    A, B, C, D, E = arr[0], arr[1], arr[2], arr[3], arr[4]

    # First set of conditions and swaps
    if A > B: # Comparison 1
        A, B = B, A
    if C > D: # Comparison 2
        C, D = D, C
    if A > C: # Comparison 3
        A, C = C, A
        B, D = D, B # Without this the algorithm will fail for [4, 5, 1, 2, 3]

    # Complex condition structure
    if E > C: # Comparison 4
        if E > D:
            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:  # 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:
            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:  # E > A
            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)

if __name__ == '__main__':
    array = [5, 3, 2, 4, 1]
    sorted_array = sort_five_elements(array)
    print(sorted_array)  # Output: [1, 2, 3, 4, 5]