TAOCP 5.3.1 Exercise 30

We work with the definitions given in the exercise.

taocpmathematicsalgorithmsvolume-3math-hard

Section 5.3.1: Minimum-Comparison Sorting

Exercise 30. [M29] (Optimum exchange sorting.) Every exchange sorting algorithm as defined in Section 5.2.2 can be represented as a comparison-exchange tree, namely a binary tree structure whose internal nodes have the form $i:j$ for $i < j$, interpreted as the following operation: "If $K_i \le K_j$, continue by taking the left branch of the tree; if $K_i > K_j$, continue by interchanging records $i$ and $j$ and then taking the right branch of the tree." When an external node is encountered, it must be true that $K_1 \le K_2 \le \cdots \le K_n$. Thus, a comparison-exchange tree differs from a comparison tree in that it specifies data movement as well as comparison operations.

Let $S_e(n)$ denote the minimum number of comparison-exchanges needed, in the worst case, to sort $n$ elements by means of a comparison-exchange tree. Prove that $S_e(n) \le S(n) + n - 1$.

Verified: no
Solve time: 4m11s

Setup

We work with the definitions given in the exercise.

  • A comparison tree for sorting (n) elements is a binary tree whose internal nodes are labeled with pairs (i:j) ((1\le i<j\le n)) representing a comparison of the original keys (K_i) and (K_j). The left branch corresponds to (K_i < K_j), the right branch to (K_i > K_j). Every external node (leaf) is labeled with a permutation (a_1 a_2\ldots a_n) indicating that the final order is (K_{a_1} < K_{a_2} < \cdots < K_{a_n}). No redundant comparisons are made, so there are exactly (n!) leaves. The minimum worst-case number of comparisons is (S(n)).

  • A comparison-exchange tree is a binary tree whose internal nodes are also labeled with pairs (i:j) ((i<j)), but now they represent the operation:
    “Compare the records currently in positions (i) and (j).
    If (K_i \le K_j), take the left branch.
    If (K_i > K_j), exchange the two records and take the right branch.”
    When an external node is reached, the array must satisfy (K_1 \le K_2 \le \cdots \le K_n).
    The minimum worst-case number of comparison-exchanges (i.e., the height of such a tree) is (S_e(n)).

We must prove (S_e(n) \le S(n) + n - 1).

Solution

Let (T) be an optimal comparison tree of height (S(n)). We construct a comparison-exchange tree (T') that sorts any input and whose height is at most (S(n) + n - 1).

1. Simulating the comparisons of (T) without losing track of the original elements

The tree (T') will initially have exactly the same branching structure as (T). For each internal node (v) of (T) we assign a pair of positions ((p_v, q_v)) (with (p_v < q_v)) that (T') will compare at the corresponding node. The assignment is done by following the unique path from the root to (v) and keeping track of how the swaps performed by (T') along that path permute the original elements.

Formally, for a node (v) let (\mathit{path}(v)) be the sequence of left/right branches from the root to (v). In (T), the comparison at (v) is between two original elements, say (x) and (y). In (T'), the array initially contains the original elements in order (1,2,\dots,n) (i.e., position (i) holds original element (i)). As we go down the tree, whenever a right branch is taken in (T'), the two compared elements are swapped. Therefore, after following (\mathit{path}(v)) the array has been permuted by the product of the transpositions corresponding to the right branches on that path. Denote this permutation by (\sigma_v); it is a bijection on ({1,\dots,n}) where (\sigma_v(i)) is the original element currently at position (i). (The empty path gives the identity permutation (\sigma_{\mathit{root}} = \mathit{id}).)

The original elements that (T) compares at (v) are (x) and (y). Their current positions in the array at node (v) are (\sigma_v^{-1}(x)) and (\sigma_v^{-1}(y)). We set [ p_v = \min\bigl(\sigma_v^{-1}(x),,\sigma_v^{-1}(y)\bigr),\qquad q_v = \max\bigl(\sigma_v^{-1}(x),,\sigma_v^{-1}(y)\bigr). ] The node (v) of (T') then performs the comparison-exchange (p_v : q_v).

Claim. For every input, the sequence of outcomes (left/right) in (T') is exactly the same as the sequence of outcomes in (T), and after each node (v) the permutation of the array in (T') is (\sigma_v).

Proof by induction on the depth of (v).
At the root, (\sigma_{\mathit{root}} = \mathit{id}), so (p_{\mathit{root}} = x), (q_{\mathit{root}} = y). The comparison is between (K_x) and (K_y), exactly as in (T). If (K_x \le K_y) both go left and no swap occurs; (\sigma) remains (\mathit{id}). If (K_x > K_y) both go right; (T') swaps the elements at positions (x) and (y), which corresponds to multiplying (\sigma) on the right by the transposition ((x;y)). This matches the definition of (\sigma) for the right child.
Now assume the claim holds for a node (v). Consider its left child (v_L) (if it exists). The path to (v_L) is (\mathit{path}(v)) followed by a left branch. By the induction hypothesis, at (v) the permutation is (\sigma_v) and the outcome at (v) was left, so no swap occurred at (v). Hence (\sigma_{v_L} = \sigma_v). The comparison at (v_L) in (T) is between some original elements (x', y'). In (T') we compare positions (\sigma_v^{-1}(x')) and (\sigma_v^{-1}(y')), which currently hold exactly those original elements. The outcome is again identical to (T)'s outcome. The right child is analogous: a right branch at (v) means a swap occurred, so (\sigma_{v_R}) is (\sigma_v) composed with the transposition of the two elements compared at (v); the same transposition is applied in (T') because the right branch triggers the exchange. ∎

Thus the part of (T') that mimics (T) has height exactly (S(n)), and at every leaf (\ell) of this part the array has been permuted to (\sigma_\ell).

2. Adding a cleanup phase at each leaf

At a leaf (\ell) of (T), the label gives the sorted order of the original elements: a permutation (\tau_\ell = (a_1, a_2, \dots, a_n)) meaning (K_{a_1} < K_{a_2} < \cdots < K_{a_n}). The target sorted array is therefore position (i) containing original element (a_i). In (T'), the array at leaf (\ell) contains the permutation (\sigma_\ell) (i.e., position (i) holds original element (\sigma_\ell(i))). We need to transform (\sigma_\ell) into (\tau_\ell).

The permutation (\pi_\ell = \sigma_\ell^{-1} \circ \tau_\ell) describes how to rearrange the current array into the target. Any permutation can be written as a product of at most (n-1) transpositions (exchanges). Choose such a decomposition (\pi_\ell = t_1 t_2 \cdots t_m) with (m \le n-1). For each transposition (t_k = (u_k; v_k)) we append a comparison-exchange node to the leaf (\ell) that compares the positions where the two elements involved in (t_k) currently reside. Because we know the exact permutation before the cleanup starts, we can compute the current positions of those two elements at each step; they are guaranteed to be out of order (otherwise the transposition would not be needed). Hence the comparison will always take the right branch and perform the exchange. The left branches of these added nodes are never taken, which is allowed in a comparison-exchange tree. After the (m) exchanges the array becomes exactly (\tau_\ell), i.e., (K_1 \le K_2 \le \cdots \le K_n).

The length of the cleanup chain for leaf (\ell) is at most (n-1). Therefore the total height of the final tree (T'') is at most (S(n) + n - 1).

Since (T'') is a valid comparison-exchange tree that sorts (n) elements, we have proved [ \boxed{S_e(n) \le S(n) + n - 1.} ]

Verification

The critical step is the simulation of (T) by the first part of (T'). We verify it independently by induction on the path length, checking that the permutation (\sigma_v) maintained in the construction exactly matches the effect of the swaps performed by (T').

Base. At the root, (\sigma_{\mathit{root}} = \mathit{id}). The comparison in (T) is (x:y); in (T') we compare positions (x) and (y). The elements there are (K_x) and (K_y). The outcomes match. If right, (T') swaps them; the new permutation is (\sigma = (x;y)), which equals the product of transpositions for the right branch.

Inductive step. Suppose at node (v) the array permutation is (\sigma_v) and the path to (v) has produced exactly the transpositions prescribed by (\sigma_v). The comparison in (T) at (v) is between original elements (x) and (y). In (T') we compare the positions that currently hold (x) and (y), namely (\sigma_v^{-1}(x)) and (\sigma_v^{-1}(y)). The values are (K_x) and (K_y), so the outcome is identical to (T).

  • If the outcome is left, no swap occurs in (T'). The permutation stays (\sigma_v), which equals the product of transpositions for the extended path (no new transposition).
  • If the outcome is right, (T') swaps the two elements. This multiplies the permutation on the right by the transposition of those two positions, which corresponds exactly to multiplying by the transposition ((x;y)) in the original element space. Hence the new permutation is (\sigma_v \cdot (\sigma_v^{-1}(x);\sigma_v^{-1}(y))), and the product of transpositions for the extended path is updated by appending ((x;y)), matching the construction.

Thus by induction the simulation is correct for every node. The cleanup phase is a standard fact: any permutation on (n) elements can be sorted with at most (n-1) exchanges (e.g., by reducing cycles). The added comparison-exchanges always take the right branch because we explicitly choose pairs that are out of order at that moment. Therefore the constructed tree is a valid comparison-exchange tree of height (\le S(n)+n-1). ∎

Notes

The proof does not require the comparison tree (T) to be optimal; any comparison tree of height (H) yields a comparison-exchange tree of height (\le H + n - 1). The bound (S_e(n) \le S(n) + n - 1) is sometimes tight, but the exercise only asks for the inequality.