TAOCP 5.3.1 Exercise 12
Let $T$ be a comparison tree with no redundant comparisons.
Section 5.3.1: Minimum-Comparison Sorting
Exercise 12. ▶ [M25] (W. G. Bouricius, circa 1954.) Suppose that equal keys may occur, but we merely want to sort the elements ${K_1, K_2, \ldots, K_n}$ so that a permutation $a_1 a_2 \ldots a_n$ is determined with $K_{a_1} \le K_{a_2} \le \cdots \le K_{a_n}$; we do not need to know whether or not equality occurs between $K_{a_i}$ and $K_{a_{i+1}}$.
Let us say that a comparison tree sorts a sequence of keys strongly if it will sort the sequence in the stated sense no matter which branch is taken below the nodes $i:j$ for which $K_i = K_j$. (The tree is binary, not ternary.)
a) Prove that a comparison tree with no redundant comparisons sorts every sequence of keys strongly if and only if it sorts every sequence of distinct keys.
b) Prove that a comparison tree sorts every sequence of keys strongly if and only if it sorts every sequence of zeros and ones strongly.
Verified: no
Solve time: 3m41s
Solution
(a)
Let $T$ be a comparison tree with no redundant comparisons.
$(\Rightarrow)$ If $T$ sorts every sequence of keys strongly, then in particular it sorts every sequence of distinct keys (where the “strongly” condition coincides with ordinary sorting, because no equalities occur).
$(\Leftarrow)$ Assume $T$ sorts every sequence of distinct keys correctly. Let $K = (K_1,\dots,K_n)$ be an arbitrary sequence of keys (possibly with equalities), and let $P$ be a path from the root to an external node that is consistent with $K$: at each internal node labelled $i{:}j$ on $P$, if $K_i < K_j$ the path goes to the left child, if $K_i > K_j$ it goes to the right child, and if $K_i = K_j$ either child may be taken. Let $\pi = (\pi_1,\pi_2,\dots,\pi_n)$ be the permutation stored at the leaf of $P$. We must prove [ K_{\pi_1} \le K_{\pi_2} \le \cdots \le K_{\pi_n}. ]
For every comparison $i{:}j$ on $P$ associate a strict inequality: left branch $\Rightarrow i \prec j$, right branch $\Rightarrow j \prec i$. Let $\prec_P$ be the transitive closure of these relations. Because $T$ has no redundant comparisons, every internal node has both subtrees non‑empty; hence there exists an assignment of distinct keys that follows $P$. Consequently $\prec_P$ is acyclic and therefore a partial order. Moreover, since $T$ correctly sorts all distinct keys, any distinct‑key assignment following $P$ must have $\pi$ as its unique sorted order. This forces $\pi$ to be the only linear extension of $\prec_P$. (If two different linear extensions existed, we could construct two distinct‑key inputs following $P$ with different sorted orders, contradicting correctness of $T$.)
The consistency of $P$ with $K$ means: for every left branch $i{:}j$ on $P$ we have $K_i \le K_j$, and for every right branch we have $K_i \ge K_j$. Thus $K$ satisfies $K_i \le K_j$ whenever $i \prec_P j$.
Embed the values of $K$ into $\mathbb{R}$ preserving order and equality; we still call the resulting vector $K$. Define the open convex cone [ C = {, x \in \mathbb{R}^n \mid x_i < x_j \text{ for all } i \prec_P j ,}. ] The consistency condition implies $K \in \overline{C}$, the closure of $C$. Because $\pi$ is the unique linear extension of $\prec_P$, the transitive closure of $\prec_P$ is exactly the total order $\pi_1 \prec \pi_2 \prec \cdots \prec \pi_n$. Hence every $x \in C$ satisfies [ x_{\pi_1} < x_{\pi_2} < \cdots < x_{\pi_n}. ] Taking closures, every $x \in \overline{C}$ satisfies the corresponding non‑strict inequalities. In particular, [ K_{\pi_1} \le K_{\pi_2} \le \cdots \le K_{\pi_n}, ] so $\pi$ is a valid sorting of $K$. Since $K$ and $P$ were arbitrary, $T$ sorts every sequence strongly. ∎
(b)
$(\Rightarrow)$ Trivial, because sequences of zeros and ones are a special case.
$(\Leftarrow)$ Let $T$ be a comparison tree that sorts every $0$‑$1$ sequence strongly. We first prove that $T$ sorts every sequence of distinct keys.
Let $K$ be a sequence of distinct keys and let $P$ be the (unique) path followed by $K$ in $T$, ending at a leaf with permutation $\pi$. Suppose, for contradiction, that $\pi$ is not the correct sorted order of $K$. Then there exist indices $a,b$ with $K_a < K_b$ but $a$ appears after $b$ in $\pi$.
Construct a $0$‑$1$ sequence $x$ by [ x_i = \begin{cases} 0 & \text{if } K_i \le K_a,\[2pt] 1 & \text{if } K_i > K_a. \end{cases} ] Because the keys are distinct, $x$ is well‑defined, $x_a = 0$, and $x_b = 1$.
Consider any comparison $i{:}j$ on $P$. Since the keys are distinct, either $K_i < K_j$ or $K_i > K_j$.
- If $K_i < K_j$, then either both $K_i,K_j \le K_a$ (so $x_i=x_j=0$), both $>K_a$ (so $x_i=x_j=1$), or $K_i \le K_a < K_j$ (so $x_i=0,; x_j=1$). In all cases $x_i \le x_j$, therefore taking the left branch (which requires $x_i \le x_j$) is a consistent choice for $x$.
- If $K_i > K_j$, a symmetric argument gives $x_i \ge x_j$, so the right branch is consistent.
Hence $P$ is a path consistent with the $0$‑$1$ sequence $x$. Because $T$ sorts all $0$‑$1$ sequences strongly, the leaf permutation $\pi$ must sort $x$, i.e. $x_{\pi_1} \le x_{\pi_2} \le \cdots \le x_{\pi_n}$. But $x_b=1$ and $x_a=0$ with $b$ before $a$ in $\pi$ yields a $1$ before a $0$, a contradiction. Therefore $\pi$ correctly sorts $K$; so $T$ sorts all distinct‑key sequences.
Now remove all redundant comparisons from $T$ (branches that can never be reached for any input, including those with equal keys). This pruning does not change the behaviour of the tree on any input that actually occurs. The resulting tree $T'$ has no redundant comparisons and still sorts all $0$‑$1$ sequences strongly. By the argument above, $T'$ sorts all distinct‑key sequences. Applying part (a) to $T'$, we conclude that $T'$ sorts every sequence strongly. Since $T$ and $T'$ are equivalent on all attainable inputs, $T$ also sorts every sequence strongly. ∎
This completes the proof. ∎