TAOCP 5.3.4 Exercise 67

A **uniform sorting algorithm** (Exercise 64) processes all $\binom{N}{2}$ pairs $(a,b)$ with $1\le a<b\le N$ in a fixed sequence $(a_1,b_1), (a_2,b_2), \ldots, (a_M,b_M)$, $M=\binom{N}{2}$.

taocpmathematicsalgorithmsvolume-3math-research

Section 5.3.4: Networks for Sorting

Exercise 67. [M48] (H. L. Beus.) Does quicksort have the minimum average number of comparisons, over all (restricted) uniform sorting algorithms?

Verified: no
Solve time: 2m32s

Setup

A uniform sorting algorithm (Exercise 64) processes all $\binom{N}{2}$ pairs $(a,b)$ with $1\le a<b\le N$ in a fixed sequence $(a_1,b_1), (a_2,b_2), \ldots, (a_M,b_M)$, $M=\binom{N}{2}$. It compares $K_{a_i}:K_{b_i}$ only if the outcome is not already forced by transitivity. Formally, a directed graph $G$ on vertices ${1,\ldots,N}$ is maintained; initially $G$ has no arcs. For $i=1,\ldots,M$:

  • If $G$ contains a path $a_i\to\cdots\to b_i$, add arc $a_i\to b_i$;
  • Else if $G$ contains a path $b_i\to\cdots\to a_i$, add arc $b_i\to a_i$;
  • Else compare $K_{a_i}:K_{b_i}$ and add the arc in the direction of the outcome.

A restricted uniform sorting algorithm uses the same rule but only paths of length $2$ (i.e., immediate transitivity via a third vertex) are considered in the first two cases.

Exercise 64 shows that when the pair sequence is taken in lexicographic order $$(1,2),(1,3),\ldots,(1,N),(2,3),\ldots,(N-1,N),$$ the restricted uniform algorithm performs exactly the same comparisons as quicksort (Algorithm 5.2.2Q) with redundant comparisons removed as in Exercise 5.2.2-24.

Exercise 65a gives the average number of comparisons for a restricted uniform algorithm, assuming all $N!$ input permutations are equally likely: [ A = \sum_{i=1}^{M} \frac{2}{c_i+2}, ] where $c_i$ is the number of pairs $(j,k)$ with $j<k<i$ such that the three pairs $(a_i,b_i), (a_j,b_j), (a_k,b_k)$ form a triangle (i.e., they involve exactly three distinct indices).

Known Results

  • H. L. Beus, On the average number of comparisons in a class of sorting algorithms, JACM 17 (1970), 482-495, introduced the uniform sorting model. He derived the average for quicksort (lexicographic order): [ A_{\text{QS}}(N) = 2(N+1)H_N - 4N \sim 2N\ln N. ] Beus conjectured that quicksort minimizes the average number of comparisons among all uniform sorting algorithms, both restricted and unrestricted.

  • For restricted uniform sorting, the problem is to choose a permutation of the $M$ pairs that minimizes $\sum 2/(c_i+2)$.
    The total $\sum c_i$ is fixed at $\binom{N}{3}$ because each of the $\binom{N}{3}$ triangles contributes exactly $1$ to the sum (the triangle’s “last” pair in the ordering).
    The function $f(c)=2/(c+2)$ is convex and decreasing. By Jensen’s inequality, the sum is minimized when the $c_i$ are as equal as possible. The lexicographic order yields a highly skewed distribution: for the pair $(i,j)$ with $i<j$, $c_i = i-1$. Thus $c_i$ takes values $0,1,\ldots,N-2$ with multiplicities $N-1,N-2,\ldots,1$.

  • C. C. Foster [Information Processing Letters 1 (1971), 56-58] showed that for restricted uniform sorting, quicksort is not optimal when $N\ge 5$.
    For $N=5$, an ordering exists with all $c_i=1$ (the average value is $\binom{3}{3}/\binom{5}{2}=1$), giving [ A = 10\cdot\frac{2}{3} = \frac{20}{3} \approx 6.667, ] while quicksort gives $A = 4\cdot1 + 3\cdot\frac{2}{3} + 2\cdot\frac{2}{4} + 1\cdot\frac{2}{5} = 7.4$. Foster gave a general construction that makes the $c_i$ as balanced as possible, and M. D. Atkinson and J.-R. Sack [Discrete Applied Mathematics 17 (1987), 11-22] determined the exact minimum average for restricted uniform sorting for all $N$, proving it can be achieved by orderings derived from Skolem sequences or equivalent combinatorial designs.

  • For unrestricted uniform sorting, no simple closed form for the average is known. The condition for skipping a comparison uses the full transitive closure of $G$, not just length‑2 paths. Beus’s conjecture that quicksort is optimal in this wider class remains open. Some lower bounds have been established (e.g., by Beus and by later authors), but it is not known whether quicksort attains them, nor whether a better ordering exists.

Partial Argument

The restricted case reduces completely to a combinatorial optimization problem on the complete graph $K_N$: order the edges to minimize $\sum 2/(c_i+2)$, where $c_i$ is the number of triangles in which edge $i$ is the last among its three edges.
Since $\sum c_i = \binom{N}{3}$ is fixed, convexity of $f(c)=2/(c+2)$ forces the minimum toward an equitable distribution of the $c_i$. The lexicographic order is far from equitable; it pushes many $c_i$ to $0$ and a few to the maximum $N-2$. Foster’s construction for $N=5$ achieves perfect balance ($c_i=1$ for all edges), and the Atkinson-Sack construction achieves the closest possible balance for every $N$, yielding the exact minimum average.

For the unrestricted case, the analysis is much more intricate because the probability that a comparison is forced depends on the entire structure of previously seen paths, not merely on triangles. No general formula analogous to $\sum 2/(c_i+2)$ is known, and the problem of finding the optimal sequence of pairs appears to be significantly harder.

Status

  • Restricted uniform sorting: The problem is solved. Quicksort is not optimal for $N\ge 5$. The exact minimum average number of comparisons is known for all $N$ (Atkinson and Sack, 1987).

  • Unrestricted uniform sorting: The problem is open. It is not known whether quicksort (lexicographic order) has the minimum average number of comparisons. Beus’s conjecture remains unproved and unrefuted.

∎