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

This is @Raymond Hettinger's solution above, but with materialized swaps, and a grand unified return statement instead of 4 that have meaningful overlap between them.

---

The if-then-else chain in the middle for incorporating _5_ ("e") has also been re-ordered to eliminate the need for the pass keyword

function sort5(_1_, _2_, _3_, _4_, _5_, _) {

    if (_2_ < (_ = _1_)) { _1_ = _2_
        _2_ =  _ }
    if (_4_ < (_ = _3_)) { _3_ = _4_
        _4_ =  _ }

    if (_3_ < (_ = _1_)) { _1_ = _3_
        _3_ =  _ ;_ = _2_; _2_ = _4_
        _4_ =  _ }

    if ((_ = _5_) <= _3_) {
            _5_ = _4_
            _4_ = _3_
        if (_1_ < _)
            _3_ = _
        else {
            _3_ = _1_
                  _1_ = _
        }
    } else if (_5_ < _4_) { _5_ = _4_
               _4_ =  _ }

    return (_1_)  (_2_ < _4_ ? (_2_ < _3_ ? (_2_)_3_ : (_3_)_2_) \
           (_4_)_5_ : (_3_)_4_ (_2_ < _5_ ? (_2_)_5_ : (_5_)_2_))
}

Answer 2

Here is an elaborate algorithm with Pseudocode and Python code.

Algorithm:

Pseudocode:

SORT_5_IN_7(A)

  // 1. Sort {A[1], A[2]} and {A[3], A[4]} with a total of 2 compares.
  if A [1] > A[2]
      reorder A[1], A[2] ⇒ A[2], A[1]
  if A[3] > A[4]
      reorder A[3], A[4] ⇒ A[4], A[3]
  
  // 2. Sort {A[1], A[2]} and {A[3], A[4]} by the first item with 1 compare.
  if A[1] > A[3]
      reorder A[1], A[2], A[3], A[4] ⇒ A[3], A[4], A[1], A[2]
  
  // 3. Sort A[5] into {A[1], A[3], A[4]} with 2 compares.
  if A[5] > A[3]
      if A[5] < A[4]
          reorder A[4], A[5] ⇒ A[5], A[4]
  else
      if A[5] > A[1]
          reorder A[3], A[4], A[5] ⇒ A[5], A[3], A[4]
      else
          reorder A[1], A[3], A[4], A[5] ⇒ A[5], A[1], A[3], A[4]
  
  // 4. Sort A[2] into {A[3], A[4], A[5]} with 2 compares.
  if A[2] > A[4]
      if A[2] > A[5]
          reorder A[2], A[3], A[4], A[5] ⇒ A[3], A[4], A[5], A[2]
      else
          reorder A[2], A[3], A[4] ⇒ A[3], A[4], A[2]
  else
      if A[2] > A[3]
          reorder A[2], A[3] ⇒ A[3], A[2]

Python code:

from itertools import permutations

def sort5in7(A):

    A = list(A)

    # 1. Sort {A[0], A[1]} and {A[2], A[3]} with a total of 2 compares.
    if A[0] > A[1]:
        A[0], A[1] = A[1], A[0]
    if A[2] > A[3]:
        A[2], A[3] = A[3], A[2]

    # 2. Sort {A[0], A[1]} and {A[2], A[3]} by the first item with 1 compare.
    if A[0] > A[2]:
        A[0], A[1], A[2], A[3] = A[2], A[3], A[0], A[1]

    # 3. Sort A[4] into {A[0], A[2], A[3]} with 2 compares.
    if A[4] > A[2]:
        if A[4] < A[3]:
            A[3], A[4] = A[4], A[3]
    else:
        if A[4] > A[0]:
            A[2], A[3], A[4] = A[4], A[2], A[3]
        else:
            A[0], A[2], A[3], A[4] = A[4], A[0], A[2], A[3]


    # 4. Sort A[1] into {A[2], A[3], A[4]} with 2 compares.
    if A[1] > A[3]:
        if A[1] > A[4]:
            A[1], A[2], A[3], A[4] = A[2], A[3], A[4], A[1]
        else:
            A[1], A[2], A[3] = A[2], A[3], A[1]
    else:
        if A[1] > A[2]:
            A[1], A[2] = A[2], A[1]

    return A

assert all(list(sort5in7(p)) == sorted(p) for p in permutations(range(5)))

perms = list(permutations(range(5)))
print("Permutation count:", len(perms))
for p in perms:
    p1 = sorted(p)
    p2 = sort5in7(p)
    print(p, p1, p2, p1 == p2)

Answer 3

This Python function sorts any input of 5 items in 6 or 7 comparisons (8 permutations need just 6 comparisons, while the remaining 112 permutations require 7):

def sort_5_items(a, b, c, d, e):
    n_comparisons = 0

    def lt(value_1, value_2):
        nonlocal n_comparisons
        n_comparisons += 1
        return value_1 < value_2

    if lt(a, b):
        if lt(c, d):
            if lt(a, c):
                if lt(c, e):
                    if lt(d, e):
                        if lt(b, d):
                            if lt(b, c):
                                return (a, b, c, d, e), n_comparisons
                            return (a, c, b, d, e), n_comparisons
                        if lt(b, e):
                            return (a, c, d, b, e), n_comparisons
                        return (a, c, d, e, b), n_comparisons
                    if lt(b, e):
                        if lt(b, c):
                            return (a, b, c, e, d), n_comparisons
                        return (a, c, b, e, d), n_comparisons
                    if lt(b, d):
                        return (a, c, e, b, d), n_comparisons
                    return (a, c, e, d, b), n_comparisons
                if lt(a, e):
                    if lt(b, c):
                        if lt(b, e):
                            return (a, b, e, c, d), n_comparisons
                        return (a, e, b, c, d), n_comparisons
                    if lt(b, d):
                        return (a, e, c, b, d), n_comparisons
                    return (a, e, c, d, b), n_comparisons
                if lt(b, c):
                    return (e, a, b, c, d), n_comparisons
                if lt(b, d):
                    return (e, a, c, b, d), n_comparisons
                return (e, a, c, d, b), n_comparisons
            if lt(a, e):
                if lt(b, e):
                    if lt(b, d):
                        if lt(d, e):
                            return (c, a, b, d, e), n_comparisons
                        return (c, a, b, e, d), n_comparisons
                    if lt(a, d):
                        return (c, a, d, b, e), n_comparisons
                    return (c, d, a, b, e), n_comparisons
                if lt(d, e):
                    if lt(a, d):
                        return (c, a, d, e, b), n_comparisons
                    return (c, d, a, e, b), n_comparisons
                if lt(b, d):
                    return (c, a, e, b, d), n_comparisons
                return (c, a, e, d, b), n_comparisons
            if lt(a, d):
                if lt(b, d):
                    if lt(c, e):
                        return (c, e, a, b, d), n_comparisons
                    return (e, c, a, b, d), n_comparisons
                if lt(c, e):
                    return (c, e, a, d, b), n_comparisons
                return (e, c, a, d, b), n_comparisons
            if lt(c, e):
                if lt(d, e):
                    return (c, d, e, a, b), n_comparisons
                return (c, e, d, a, b), n_comparisons
            return (e, c, d, a, b), n_comparisons
        if lt(a, d):
            if lt(d, e):
                if lt(c, e):
                    if lt(b, c):
                        if lt(b, d):
                            return (a, b, d, c, e), n_comparisons
                        return (a, d, b, c, e), n_comparisons
                    if lt(b, e):
                        return (a, d, c, b, e), n_comparisons
                    return (a, d, c, e, b), n_comparisons
                if lt(b, e):
                    if lt(b, d):
                        return (a, b, d, e, c), n_comparisons
                    return (a, d, b, e, c), n_comparisons
                if lt(b, c):
                    return (a, d, e, b, c), n_comparisons
                return (a, d, e, c, b), n_comparisons
            if lt(a, e):
                if lt(b, d):
                    if lt(b, e):
                        return (a, b, e, d, c), n_comparisons
                    return (a, e, b, d, c), n_comparisons
                if lt(b, c):
                    return (a, e, d, b, c), n_comparisons
                return (a, e, d, c, b), n_comparisons
            if lt(b, c):
                if lt(b, d):
                    return (e, a, b, d, c), n_comparisons
                return (e, a, d, b, c), n_comparisons
            return (e, a, d, c, b), n_comparisons
        if lt(a, e):
            if lt(b, e):
                if lt(b, c):
                    if lt(c, e):
                        return (d, a, b, c, e), n_comparisons
                    return (d, a, b, e, c), n_comparisons
                if lt(a, c):
                    return (d, a, c, b, e), n_comparisons
                return (d, c, a, b, e), n_comparisons
            if lt(c, e):
                if lt(a, c):
                    return (d, a, c, e, b), n_comparisons
                return (d, c, a, e, b), n_comparisons
            if lt(b, c):
                return (d, a, e, b, c), n_comparisons
            return (d, a, e, c, b), n_comparisons
        if lt(a, c):
            if lt(b, c):
                if lt(d, e):
                    return (d, e, a, b, c), n_comparisons
                return (e, d, a, b, c), n_comparisons
            if lt(d, e):
                return (d, e, a, c, b), n_comparisons
            return (e, d, a, c, b), n_comparisons
        if lt(c, e):
            return (d, c, e, a, b), n_comparisons
        if lt(d, e):
            return (d, e, c, a, b), n_comparisons
        return (e, d, c, a, b), n_comparisons
    if lt(c, d):
        if lt(a, d):
            if lt(a, e):
                if lt(a, c):
                    if lt(c, e):
                        if lt(d, e):
                            return (b, a, c, d, e), n_comparisons
                        return (b, a, c, e, d), n_comparisons
                    return (b, a, e, c, d), n_comparisons
                if lt(b, c):
                    if lt(d, e):
                        return (b, c, a, d, e), n_comparisons
                    return (b, c, a, e, d), n_comparisons
                if lt(d, e):
                    return (c, b, a, d, e), n_comparisons
                return (c, b, a, e, d), n_comparisons
            if lt(b, e):
                if lt(c, e):
                    if lt(b, c):
                        return (b, c, e, a, d), n_comparisons
                    return (c, b, e, a, d), n_comparisons
                if lt(a, c):
                    return (b, e, a, c, d), n_comparisons
                return (b, e, c, a, d), n_comparisons
            if lt(b, c):
                if lt(a, c):
                    return (e, b, a, c, d), n_comparisons
                return (e, b, c, a, d), n_comparisons
            if lt(c, e):
                return (c, e, b, a, d), n_comparisons
            return (e, c, b, a, d), n_comparisons
        if lt(d, e):
            if lt(a, e):
                if lt(b, c):
                    return (b, c, d, a, e), n_comparisons
                if lt(b, d):
                    return (c, b, d, a, e), n_comparisons
                return (c, d, b, a, e), n_comparisons
            if lt(b, d):
                if lt(b, c):
                    return (b, c, d, e, a), n_comparisons
                return (c, b, d, e, a), n_comparisons
            if lt(b, e):
                return (c, d, b, e, a), n_comparisons
            return (c, d, e, b, a), n_comparisons
        if lt(c, e):
            if lt(b, e):
                if lt(b, c):
                    return (b, c, e, d, a), n_comparisons
                return (c, b, e, d, a), n_comparisons
            if lt(b, d):
                return (c, e, b, d, a), n_comparisons
            return (c, e, d, b, a), n_comparisons
        if lt(b, c):
            if lt(b, e):
                return (b, e, c, d, a), n_comparisons
            return (e, b, c, d, a), n_comparisons
        if lt(b, d):
            return (e, c, b, d, a), n_comparisons
        return (e, c, d, b, a), n_comparisons
    if lt(a, c):
        if lt(a, e):
            if lt(a, d):
                if lt(c, e):
                    return (b, a, d, c, e), n_comparisons
                if lt(d, e):
                    return (b, a, d, e, c), n_comparisons
                return (b, a, e, d, c), n_comparisons
            if lt(b, d):
                if lt(c, e):
                    return (b, d, a, c, e), n_comparisons
                return (b, d, a, e, c), n_comparisons
            if lt(c, e):
                return (d, b, a, c, e), n_comparisons
            return (d, b, a, e, c), n_comparisons
        if lt(b, e):
            if lt(d, e):
                if lt(b, d):
                    return (b, d, e, a, c), n_comparisons
                return (d, b, e, a, c), n_comparisons
            if lt(a, d):
                return (b, e, a, d, c), n_comparisons
            return (b, e, d, a, c), n_comparisons
        if lt(b, d):
            if lt(a, d):
                return (e, b, a, d, c), n_comparisons
            return (e, b, d, a, c), n_comparisons
        if lt(d, e):
            return (d, e, b, a, c), n_comparisons
        return (e, d, b, a, c), n_comparisons
    if lt(c, e):
        if lt(a, e):
            if lt(b, c):
                if lt(b, d):
                    return (b, d, c, a, e), n_comparisons
                return (d, b, c, a, e), n_comparisons
            return (d, c, b, a, e), n_comparisons
        if lt(b, c):
            if lt(b, d):
                return (b, d, c, e, a), n_comparisons
            return (d, b, c, e, a), n_comparisons
        if lt(b, e):
            return (d, c, b, e, a), n_comparisons
        return (d, c, e, b, a), n_comparisons
    if lt(d, e):
        if lt(b, e):
            if lt(b, d):
                return (b, d, e, c, a), n_comparisons
            return (d, b, e, c, a), n_comparisons
        if lt(b, c):
            return (d, e, b, c, a), n_comparisons
        return (d, e, c, b, a), n_comparisons
    if lt(b, d):
        if lt(b, e):
            return (b, e, d, c, a), n_comparisons
        return (e, b, d, c, a), n_comparisons
    if lt(b, c):
        return (e, d, b, c, a), n_comparisons
    return (e, d, c, b, a), n_comparisons

Derivation

from typing import Set, List, Tuple
from string import ascii_letters
from itertools import permutations, combinations

def build_decision_tree(initial_permutations: Set[int],
                           conditional_permutations: List[Set[Tuple[int]]]):
    if len(initial_permutations) == 1:
        return initial_permutations.pop()

    # Find condition that splits `initial_permutations` in the most balanced way.
    target = len(initial_permutations) / 2
    condition_index = 0
    condition_sizes = [len(initial_permutations & perms)
                       for perms in conditional_permutations]

    condition_index = min(range(len(conditional_permutations)),
                          key = lambda i: abs(condition_sizes[i] - target))

    permutations_true = initial_permutations & conditional_permutations[condition_index]
    permutations_false = initial_permutations - permutations_true

    return (condition_index,
            (build_decision_tree(permutations_true, conditional_permutations),
             build_decision_tree(permutations_false, conditional_permutations)))

def get_sort_function_string(decision_tree, conditions, indent=4):
    indentation = " " * indent
    if isinstance(decision_tree[1], int):
        return_statement = f"return {', '.join([ascii_letters[x] for x in decision_tree])}\n"
        return indentation + return_statement
    else:
        i, j = conditions[decision_tree[0]]
        condition_string = f"{indentation}if {ascii_letters[i]} < {ascii_letters[j]}:\n"
        true_subtree, false_subtree = decision_tree[1]
        true_subtree_string = get_sort_function_string(true_subtree, conditions, indent + 4)
        false_subtree_string = get_sort_function_string(false_subtree, conditions, indent)
        return condition_string + true_subtree_string + false_subtree_string

def generate_sorting_logic(n_items: int):
    permutations_n = set(permutations(range(n_items)))
    conditions = list(combinations(range(n_items), 2))
    conditional_permutations = [{p for p in permutations_n if p.index(i) < p.index(j)}
                                for i, j in conditions]

    tree = build_decision_tree(permutations_n, conditional_permutations)

    function_arguments = ", ".join([ascii_letters[i] for i in range(n_items)])
    function_header = f"def sort_{n_items}_items({function_arguments}):\n"
    return function_header + get_sort_function_string(tree, conditions)

def check_sorter(n_items, sorter):
    sorted_range = tuple(range(n_items))
    for p in permutations(range(n_items)):
        sorted_p_actual = sorter(*p)
        assert sorted_p_actual == sorted_range, f"Expected {sorted_range}, got {sorted_p_actual}"

    print(f"All permutations of {n_items} items were sorted correctly.")

n_items = 5
sorter_string = generate_sorting_logic(n_items)
#print(sorter_string)
exec(sorter_string)
check_sorter(n_items, eval(f"sort_{n_items}_items"))

We can see that the above derivation (which chooses comparisons that block out half the possibilities after each comparison) produces sorting functions that have a time complexity of O(log(n!)), which is equivalent to O(nlogn).

Further reading: Number of comparisons required to sort a list (table)

Answer 4

Five items can be sorted with at most seven comparisons, because log2(5!) = 6.9. I suggest checking if any standard sorting 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 using this algorithm to find the comparison sequence:

1. Create a list with all 120 permutations of [1..5].
2. Try all (initially 5 * 4 = 20) possible comparisons and choose the one which splits the list into two most equally sized lists.
3. Apply this split, then:
   • if the two splits contain only one element, terminate
   • otherwise, go to 2.

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 an increasing amount of comparisons. 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 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
    swap B, D  # Thanks Deqing!

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

For sorting networks, it is not possible to have less than 9 comparisons to sort 5 items when the input is not known. The lower bound has been proven for sorting networks up to 10. See https://en.wikipedia.org/wiki/Sorting_network.

Correctness of sorting networks could be verified by the Zero-one principle as mentioned in The Art of Computer Programming, Vol 3 by Knuth. That is, if a sorting network can correctly sort all permutations of 0s and 1s, then it is a correct sorting network. None of the algorithms mentioned on this post passed the Zero-one test.

In addition, the lower bound says that comparison based sorts cannot have less than ceil(log(n!)) comparators to correctly sort, however, it does not mean that this is achievable.

Answer 7

Here is C++ implementation which sorts 5 elements in <= 7 comparisons. Was able to find 8 cases which can be sorted in 6 comparisons. That makes sense if we imagine full binary tree with 120 leaf nodes, there will be 112 nodes at level 7 and 8 leaf nodes at level 6. Here is the full code that is tested to work for all possible permutations.

#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <numeric>

using namespace std;

ostream& operator << ( ostream& os, vector<int> v )
{
    cout << "[ ";
    for ( auto x: v ) cout << x << ' ';
    cout << "]";
    return os;
}

class Comp {
    int count;
public:
    Comp(): count{0}{}
    bool isLess( vector<int> v, int i, int j ) {
        count++;
        //cout << v << "Comparison#" << count << ": " << i << ", " << j << endl;
        return v[ i ] < v[ j ];
    }
    int getCount() { return count; }
};


int mySort( vector<int> &v )
{
    Comp c;
    if ( c.isLess( v, 1, 0 ) ) {
        swap( v[ 0 ], v[ 1 ] );
    }
    if ( c.isLess( v, 3, 2 ) ) {
        swap( v[ 2 ], v[ 3 ] );
    }
    // By now (0, 1) (2, 3) (4)
    if ( c.isLess( v, 0, 2 ) ) {
        // ( 0, 2, 3 ) (1)
        swap( v[ 1 ], v[ 2 ] );
        swap( v[ 2 ], v[ 3 ] );
    } else {
        // ( 2, 0, 1 ) ( 3 )
        swap( v[ 1 ], v[ 2 ] );
        swap( v[ 0 ], v[ 1 ] );
    }
    // By now sorted order ( 0, 1, 2 ) ( 3 ) ( 4 ) and know that 3 > 0
    if ( c.isLess( v, 4, 1 ) ) {
        if ( c.isLess( v, 4, 0 ) ) {
            // ( 4, 0, 1, 2 ) ( 3 ) ( ... )
            v.insert( v.begin(), v[4] );
            // By now ( 0, 1, 2, 3 ) ( 4 ) ( ... ) and know that 4 > 1
            if ( c.isLess( v, 4, 2 ) ) {
                // ( 0, 1, 4, 2, 3 ) ( ... )
                v.insert( v.begin() + 2, v[4] );
            } else {
                if ( c.isLess( v, 4, 3 ) ) {
                    // ( 0, 1, 2, 4, 3 ) ( ... )
                    v.insert( v.begin() + 3, v[4] );
                } else {
                    // ( 0, 1, 2, 3, 4 ) ( ... )
                    v.insert( v.begin() + 4, v[4] );
                }
            }
            // ( 1 2 3 4 5 ) and trim the rest
            v.erase( v.begin()+5, v.end() );
            return c.getCount(); /////////// <--- Special case we could been done in 6 comparisons
        } else {
            // ( 0, 4, 1, 2 ) ( 3 ) ( ... ) 
            v.insert( v.begin() + 1, v[4] );
        }
    } else {
        if ( c.isLess( v, 4, 2 ) ) {
            // ( 0, 1, 4, 2 ) ( 3 ) ( ... )
            v.insert( v.begin() + 2, v[4] );
        } else {
            // ( 0, 1, 2, 4 ) ( 3 ) ( ... )
            v.insert( v.begin() + 3, v[4] );
        }
    }
    // By now ( 0, 1, 2, 3 ) ( 4 )( ... ): with 4 > 0
    if ( c.isLess( v, 4, 2 ) ) {
        if ( c.isLess( v, 4, 1 ) ) {
            // ( 0, 4, 1, 2, 3 )( ... )
            v.insert( v.begin() + 1, v[4] );
        } else {
            // ( 0, 1, 4, 2, 3 )( ... )
            v.insert( v.begin() + 2, v[4] );
        }
    } else {
        if ( c.isLess( v, 4, 3 ) ) {
            // ( 0, 1, 2, 4, 3 )( ... )
            v.insert( v.begin() + 3, v[4] );
        } else {
            // ( 0, 1, 2, 3, 4 )( ... )
            v.insert( v.begin() + 4, v[4] );
        }
    }
    v.erase( v.begin()+5, v.end() );
    return c.getCount();
}

#define TEST_ALL
//#define TEST_ONE

int main()
{
#ifdef TEST_ALL
    vector<int> v1(5);
    iota( v1.begin(), v1.end(), 1 );
    do {
        vector<int> v2 = v1, v3 = v1;
        int count = mySort( v2 );
        if ( count == 6 )
            cout << v3 << " => " << v2 << " #" << count << endl;
    } while( next_permutation( v1.begin(), v1.end() ) );
#endif

#ifdef TEST_ONE
    vector<int> v{ 1, 2, 3, 1, 2};
    mySort( v );
    cout << v << endl;
#endif
}

Answer 8

I have written a C implementation of the solution to this problem which can be found here: Sorting 5 elements using 7 comparisons

My code is well commented with an explanation of why it is working.

Answer 9

FWIW, here's a compact and easy to follow Python version with tests to make sure it works:

def sort5(a, b, c, d, e):
    'Sort 5 values with 7 Comparisons'
    if a < b:      a, b = b, a
    if c < d:      c, d = d, c
    if a < c:      a, b, c, d = c, d, a, b
    if e < c:
        if e < d:  pass
        else:      d, e = e, d
    else:
        if e < a:  c, d, e = e, c, d
        else:      a, c, d, e = e, a, c, d
    if b < d:
        if b < e:  return b, e, d, c, a
        else:      return e, b, d, c, a
    else:
        if b < c:  return e, d, b, c, a
        else:      return e, d, c, b, a

if __name__ == '__main__':
    from itertools import permutations

    assert all(list(sort5(*p)) == sorted(p) for p in permutations(range(5)))

Answer 10

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 11

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 12

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 13

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 14

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 15

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 16

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.