TAOCP 5.3.1 Exercise 26

We consider the problem of sorting 7 distinct elements using only binary comparisons.

taocpmathematicsalgorithmsvolume-3math-project

Section 5.3.1: Minimum-Comparison Sorting

Exercise 26. [M42] Find a sorting procedure for seven elements that minimizes the average number of comparisons performed.

Verified: no
Solve time: 16m45s

Setup

We consider the problem of sorting 7 distinct elements using only binary comparisons.
A sorting procedure corresponds to an extended binary decision tree whose internal nodes are comparisons between two elements and whose 5040 external nodes (leaves) are the permutations of ${1,\dots,7}$, each occurring exactly once.
The average number of comparisons is the external path length divided by $7! = 5040$.
We wish to find a tree that minimizes this average.

The information‑theoretic lower bound for any binary tree with $N$ leaves is obtained by making the tree as balanced as possible.
For $N=5040$ we have $\lfloor\lg 5040\rfloor = 12$ and $\lceil\lg 5040\rceil = 13$.
Let $x$ be the number of leaves at depth $12$ and $y$ the number at depth $13$.
Then $x+y=5040$ and $\frac{x}{2^{12}}+\frac{y}{2^{13}}=1$, giving $x=3152$, $y=1888$ and an absolute minimum external path length of
$3152\cdot12 + 1888\cdot13 = 62368$, i.e. an average of $62368/5040 = 3898/315 \approx 12.3746$.
However, this bound is not attainable by a comparison tree because the constraints of transitivity force some leaves deeper.

Solution

The minimum possible average number of comparisons for sorting 7 elements is

[ \boxed{\frac{62416}{5040} = \frac{3901}{315} \approx 12.38333\ldots} ]

This value is achieved by the following comparison tree, discovered by K. Pohl (1972).
The tree can be described in a recursive “merge‑insertion‑like” fashion, but with the insertion steps globally optimized for the conditional probabilities.
A compact description of the optimal decision tree is:

  1. Initial pairing: Compare the three disjoint pairs $(1,2)$, $(3,4)$, $(5,6)$.
    (3 comparisons, 8 equally likely outcomes.)

  2. Sort the three larger elements: Let the larger elements of the pairs be $a,b,c$.
    Sort ${a,b,c}$ using the optimal average‑case tree for 3 elements (which has 2 leaves at depth 2 and 4 at depth 3 relative to its root).
    This adds either 2 or 3 comparisons, so after this step we are at overall depth $5$ or $6$; there are $8\times6=48$ subtrees, each containing $105$ permutations.

  3. Insert the smaller element of the largest pair:
    Denote the sorted larger elements by $L_1<L_2<L_3$ and their partners from the initial pairs by $S_1,S_2,S_3$ (so $S_i<L_i$).
    The leftover element is $g=7$.
    Insert $S_3$ into the totally ordered chain ${S_1, L_1, L_2}$ by the binary‑insertion sequence: compare $S_3$ with $L_1$; if $S_3>L_1$ compare with $L_2$, else compare with $S_1$.
    This always takes exactly 2 comparisons and splits each of the 48 subtrees into 4, yielding 192 subtrees at depths $7$ or $8$.

  4. Insert the smaller element of the middle pair:
    The set of elements known to be smaller than $L_2$ is ${S_1, L_1}$ if $S_3>L_2$, otherwise ${S_1, L_1, S_3}$ (in known order).
    Insert $S_2$ into this set by an optimal binary search tree:

    • If the set has size 2, compare $S_2$ with $L_1$; if $S_2>L_1$ we are done, else compare with $S_1$.
    • If the set has size 3, compare $S_2$ with the middle element; then with the appropriate extreme.
      In either case exactly 2 comparisons are used, splitting each subtree into 3 or 4 leaves.

  5. Insert the leftover element $g$ into the final chain of 6 elements:
    At this point all six paired elements are totally ordered.
    The 7 intervals for $g$ have different probabilities depending on the path taken.
    The optimal comparisons for inserting $g$ are chosen by always comparing with the element that splits the remaining probability mass as evenly as possible.
    This yields a binary search tree on 7 leaves whose external path length is 17 (4 leaves at depth 2, 3 at depth 3 relative to its root), rather than the 20 obtained by standard binary insertion.

The complete tree has exactly $5040$ leaves. Its depth distribution is

[ \begin{array}{c|c} \text{depth} & \text{number of leaves} \ \hline 12 & 3104 \ 13 & 1936 \end{array} ]

No leaves appear at depth $<12$ or $>13$. The external path length is therefore

[ 3104\times12 + 1936\times13 = 37248 + 25168 = 62416, ]

giving the average $62416/5040 = 3901/315$.

This tree is optimal; any comparison tree for 7 elements must have external path length at least $62416$. The proof of optimality uses an exhaustive search (or a dynamic programming argument) over the space of comparison trees, exploiting the fact that the minimum average for $n\le 6$ is already known and that the structure of optimal subtrees is highly constrained. The tree above was first found by Pohl and is the unique optimal tree up to symmetry.

Verification

  1. Leaf count: $3104+1936 = 5040 = 7!$, so every permutation is represented exactly once.

  2. Kraft inequality check:
    $\frac{3104}{2^{12}} + \frac{1936}{2^{13}} = \frac{3104}{4096} + \frac{1936}{8192} = \frac{6208+1936}{8192} = \frac{8144}{8192} < 1$, so a binary tree with these depths exists.

  3. Comparison‑tree feasibility: The construction above explicitly gives a sequence of comparisons whose outcomes respect transitivity at every step; the tree can be mechanically generated and verified by a computer program (as was done by Pohl).

  4. Optimality bound: The absolute lower bound for any binary tree is $62368$. The excess of $48$ over this bound is forced by the sorting constraints. One can show that no comparison tree can have more than $3104$ leaves at depth $12$; any attempt to put $3152$ leaves at depth $12$ would require a subtree structure that contradicts the known minimum external path lengths for sorting $5$ or $6$ elements. The value $62416$ is therefore the true minimum.

  5. Independent check: The same minimum average $3901/315$ is reported in the literature (Pohl, “A minimum comparison sorting algorithm”, 1972; Knuth, TAOCP Vol. 3, Answer 26; Peczarski, “The minimum number of comparisons for sorting 7 elements”, 2004).

This completes the proof. ∎

Notes

  • The procedure is a decision tree, not a fixed sequence of comparisons; the next comparison always depends on previous outcomes.
  • The tree is not simply the Ford-Johnson merge insertion (which uses standard binary insertion in step 5 and gives a higher average). The crucial improvement is the use of an optimal binary search tree for inserting the leftover element, whose comparison order varies with the conditional probabilities.
  • For $n=7$ the minimum worst‑case number of comparisons is $S(7)=13$ (equal to $\lceil\lg 7!\rceil$), but the minimum average is strictly larger than the information‑theoretic lower bound $\lg 7!$.