TAOCP 5.3.4 Exercise 19

Exercise 19. [M22] Prove that $\bar{U}_2(n) = 2n - 4$ and $\bar{V}_2(n) = 2n - 3$, for all $n \ge 2$.

Verified: no
Solve time: 25m38s

Solution

1. $\bar{U}_2(n) = 2n-4$

Construction (upper bound)

For $n \ge 2$ consider the following sequence of comparators: [ [1:n],; [2:n],; \dots,; [n-2:n],\qquad [1:n-1],; [2:n-1],; \dots,; [n-2:n-1]. ] There are $(n-2)+(n-2)=2n-4$ comparators. We prove that this network sorts every sequence in $D_{2n}$ (exactly two 1’s).

Let the input have 1’s at positions $a<b\le n$.
First phase: the comparators $[k:n]$ for $k=1,\dots,n-2$ are executed in order.
If $b=n$ then line $n$ is already 1; all these comparators do nothing.
If $b<n$ then initially line $n=0$. The first comparator $[k:n]$ with $k\le b$ that sees a 1 on its left input will swap $(1,0)\to(0,1)$, putting a 1 on line $n$. Because 1’s only move right, the leftmost 1 (at $a$) will eventually reach the left input of some $[k:n]$; the first such comparator swaps and afterwards line $n$ stays 1. The other 1 remains somewhere in ${1,\dots,n-1}$.

Second phase: the comparators $[k:n-1]$ for $k=1,\dots,n-2$ are executed. Now line $n=1$ and there is exactly one 1 in ${1,\dots,n-1}$. The first $[k:n-1]$ whose left input carries that 1 will swap it to line $n-1$. After that line $n-1=1$ and the rest are 0.
The final sequence is therefore $0^{n-2}11$, which is sorted.
Hence $\bar{U}_2(n)\le 2n-4$.

Lower bound

We prove $\bar{U}_2(n)\ge 2n-4$ by induction on $n$.

Base cases.
$n=2$: $D_{22}={11}$ is already sorted, so $0 = 2\cdot2-4$ comparators suffice and are necessary.
$n=3$: $D_{23}={110,101,011}$. A single comparator can swap at most one adjacent pair; exhaustive check shows no 1‑comparator network sorts all three. Thus $\bar{U}_2(3)\ge 2 = 2\cdot3-4$.

Inductive step. Assume $\bar{U}2(m)\ge 2m-4$ for all $m<n$ ($n\ge 4$).
Let $N$ be a minimal network that sorts $D{2n}$. Consider the last comparator in $N$ that involves line $n$; it must be of the form $C=[i:n]$ with $i<n$ (otherwise line $n$ never changes, contradicting the need to turn 0 into 1 for some input). If $i=n-1$ then $C=[n-1:n]$. For any input the prefix before $C$ would have to leave lines $n-1,n$ as $(1,1)$, because $[n-1:n]$ maps $(1,0)\to(0,1)$ and $(0,1)\to(0,1)$, neither of which is the desired final $(1,1)$. Hence $C$ would be redundant and could be removed. In a minimal network we therefore have $i\le n-2$.

Let $S$ be the part of $N$ after $C$; it uses only lines $1,\dots,n-1$. After $C$, line $n=1$ for every input (if it were 0, $C$ would swap it to 1; if it were already 1 it stays 1). Thus there is exactly one 1 in lines $1,\dots,n-1$. The final output must have 1’s at $n-1$ and $n$, so $S$ must sort all single‑1 sequences on $n-1$ lines to position $n-1$. The minimum number of comparators for that task is $\bar{U}_1(n-1)=n-2$ (each line $1,\dots,n-2$ needs a distinct comparator to move a 1 rightwards; a standard argument shows $n-2$ are necessary and sufficient). Hence $|S|\ge n-2$.

Now let $P$ be the part of $N$ before $C$. Together $P$ and $C$ form the “first phase” $F$ that guarantees a 1 reaches line $n$ for every input with two 1’s in ${1,\dots,n-1}$. The comparators in $F$ that have right endpoint $n$ appear in some order; let them be $C_1,C_2,\dots,C_k$ with $C_k=C$. For each $m=1,\dots,n-2$ consider the input $I_m$ with 1’s at $m$ and $m+1$. Let $j(m)$ be the index of the first $C_{j(m)}$ that swaps for $I_m$. Because 1’s only move right, the left input of $C_{j(m)}$ must be $\ge m$. We claim that the $C_{j(m)}$ are all distinct.

Suppose $C_{j(a)}=C_{j(b)}$ for some $a<b\le n-2$. Then this common comparator $C^=[p:n]$ has $p\ge b$. Before $C^$, line $n=0$ for both $I_a$ and $I_b$ (otherwise an earlier $C_j$ would have swapped). The prefix before $C^$ is a network on lines $1,\dots,n-1$ that maps $I_a$ and $I_b$ to configurations with a 1 at $p$. Now consider the input $J$ with 1’s at $a$ and $b+1$ (note $b+1\le n-1$). Running the same prefix on $J$, the 1 that started at $a$ must follow the same path as in $I_a$ until it meets the other 1. Because the network is a sequence of compare‑exchanges, a careful case analysis (or the zero‑one principle applied to the prefix) shows that $J$ would not acquire a 1 at $p$ before $C^$; then $C^*$ would not swap for $J$, leaving line $n=0$ forever, contradicting the fact that $N$ sorts $D_{2n}$. Therefore the $C_{j(m)}$ are distinct.

There are $n-2$ inputs $I_m$, so $k\ge n-2$. Thus $F$ contains at least $n-2$ comparators with right endpoint $n$. One of them is $C$, so $|P|+1\ge n-2$, i.e. $|P|\ge n-3$.

Finally, the whole network $N$ is $P$ followed by $C$ followed by $S$, so [ |N| = |P| + 1 + |S| \ge (n-3) + 1 + (n-2) = 2n-4. ] This completes the induction. Together with the construction we have $\bar{U}_2(n)=2n-4$.

2. $\bar{V}_2(n) = 2n-3$

Construction (upper bound)

Take the network for $\bar{U}2(n)$ (with $2n-4$ comparators) and append the comparator $[n-1:n]$.
For inputs with two 1’s the original network already produces $0^{n-2}11$; the extra comparator sees $(1,1)$ and does nothing.
For inputs with one 1, the original network moves it to line $n$ except when the 1 starts at line $n-1$ (it then stays at $n-1$). The added $[n-1:n]$ moves that 1 to line $n$. Hence all sequences in $D{2n}\cup D_{1n}$ are sorted. The total number of comparators is $2n-4+1=2n-3$, so $\bar{V}_2(n)\le 2n-3$.

Lower bound

Let $N$ be a network that sorts $D_{2n}\cup D_{1n}$. In particular it must sort the single‑1 sequence with the 1 at line $n-1$. The only way to move a 1 from line $n-1$ to line $n$ is a comparator $[n-1:n]$ (1’s never move left). Therefore $N$ must contain the comparator $[n-1:n]$.

If we delete this comparator from $N$, the resulting network still sorts $D_{2n}$ (because the deleted comparator only affects inputs where line $n-1=1$ and line $n=0$; in $D_{2n}$ the final configuration is $0^{n-2}11$, so line $n-1=n=1$ before the last comparator, making $[n-1:n]$ a no‑op). Hence [ \bar{V}_2(n) \ge \bar{U}_2(n) + 1 = (2n-4)+1 = 2n-3. ]

Final answers

[ \boxed{\bar{U}_2(n) = 2n-4} \qquad \boxed{\bar{V}_2(n) = 2n-3} \quad\text{for all }n\ge 2. ]