TAOCP 5.3.4 Exercise 17

Section 5.3.4: Networks for Sorting

Exercise 17. [M25] Let $D_{tn}$ be the set of all $\binom{n}{2}$ sequences $\langle x_1,\ldots,x_n\rangle$ of 0s and 1s having exactly $t$ 1s. Show that $\bar{U}t(n)$ is the minimum number of comparators needed in a network that sorts all the elements of $D{tn}$; $\bar{V}t(n)$ is the minimum number needed to sort $D{tn} \cup D_{(t-1)n}$; and $\bar{W}t(n)$ is the minimum number needed to sort $\bigcup{0 \le s \le t} D_{sn}$.

Verified: no
Solve time: 3m32s

Solution

The quantities $\bar{U}_t(n)$, $\bar{V}_t(n)$, $\bar{W}_t(n)$ are defined in the text as the minimum number of comparators required in a standard network (i.e., a network in which every comparator $[i:j]$ satisfies $i<j$) that sorts the respective sets of $0$-$1$ sequences. We must show that these same numbers are also the minima when the requirement “standard” is dropped - that is, they are the minima over all comparator networks.

Let $D_{tn}$ denote the set of $\binom{n}{t}$ sequences of length $n$ containing exactly $t$ ones.
Observe that $D_{tn}$ is invariant under any permutation of the $n$ lines: permuting the coordinates of a sequence with exactly $t$ ones yields another sequence with exactly $t$ ones. The same holds for the sets
$D_{tn} \cup D_{(t-1)n}$ and $\bigcup_{0\le s\le t} D_{sn}$; they are unions of such permutation‑invariant sets and therefore are themselves invariant under arbitrary permutations of the lines.

Now take any network $N$ (not necessarily standard) that sorts one of these sets, say $D_{tn}$. Apply the standardisation algorithm of Exercise 16 to $N$. That algorithm repeatedly finds the first comparator $[i:j]$ with $i>j$, replaces it by $[j:i]$, and swaps the labels $i$ and $j$ in all subsequent comparators. Each such step is equivalent to inserting a transposition of the two lines $i$ and $j$ at that stage of the network. Because the set $D_{tn}$ is invariant under every transposition, the network obtained after the step sorts $D_{tn}$ if and only if the original network did. By induction on the number of non‑standard comparators, the final standard network $N'$ produced by the algorithm also sorts $D_{tn}$. The algorithm does not change the total number of comparators.

Consequently, for every network that sorts $D_{tn}$ there exists a standard network with the same number of comparators that also sorts $D_{tn}$. Hence the minimum number of comparators over all networks equals the minimum over standard networks, which by definition is $\bar{U}_t(n)$.

Exactly the same reasoning applies to the sets $D_{tn} \cup D_{(t-1)n}$ and $\bigcup_{0\le s\le t} D_{sn}$ because they too are invariant under all permutations of the lines. Therefore $\bar{V}_t(n)$ and $\bar{W}_t(n)$ are likewise the unrestricted minima for their respective sets.

This completes the proof. ∎