TAOCP 5.3.4 Exercise 45

Section 5.3.4: Networks for Sorting

Exercise 45. [M20] Prove that any $(1, n)$-merging network without multiple fanout must have at least $\lceil \lg(n + 1) \rceil$ levels of delay.

Verified: no
Solve time: 13m09s

Solution

We prove the lower bound by using the zero‑one principle and analyzing the information flow in a comparator network without multiple fanout.

Zero‑one principle

By the zero‑one principle (see Section 5.3.4), a comparator network correctly merges all real‑valued sequences iff it correctly merges all sequences of 0s and 1s. For a ((1,n))‑merge the inputs are a single element (x) and a sorted sequence (y_1 \le y_2 \le \cdots \le y_n). When the inputs are 0s and 1s, the (y)‑sequence consists of (k) zeros followed by (n-k) ones for some (k \in {0,1,\dots,n}), and (x \in {0,1}). There are exactly (2(n+1)) such zero‑one inputs.

Structure of a network without multiple fanout

“No multiple fanout means that each wire is used as input to at most one comparator. Consequently the network is a collection of disjoint binary trees when viewed from the inputs to the outputs. In particular, the wire that initially carries (x) follows a unique path through the network; let the comparators on this path be (C_1, C_2, \dots, C_\ell) in order of their levels. Because the total depth of the network is (D), we have (\ell \le D).

Disjoint subnetworks feeding the comparators on (x)’s path

At comparator (C_i) the value (x) is compared with the value on some other wire. That wire comes from a subnetwork that processes only the (y)’s (if it involved (x), the wire carrying (x) would have to split, which would require multiple fanout). The depth of this subnetwork is at most (i-1) because it must finish before level (i). Since the network has no multiple fanout, the sets of (y)‑inputs that feed into the subnetworks for (C_1, C_2, \dots, C_\ell) are pairwise disjoint.

Capacity of a subnetwork of depth (d)

In a comparator network without multiple fanout, any output wire of depth (d) can depend on at most (2^d) input wires. This follows by a simple induction: a wire at depth (0) depends on exactly (1) input; each comparator combines two wires, doubling the maximum number of inputs. Hence the subnetwork feeding (C_i) can contain at most (2^{i-1}) distinct (y)‑inputs.

Bounding the number of (y)’s that interact with (x)

Summing over all comparators on (x)’s path, the total number of (y)’s that ever interact (directly or indirectly) with (x) is at most [ \sum_{i=1}^\ell 2^{i-1} \le \sum_{i=1}^D 2^{i-1} = 2^D - 1. ]

Every (y) must interact with (x)

Suppose some (y_j) never interacts with (x). Then there is no directed path of comparators connecting (x) and (y_j). In a network without multiple fanout, the wiring is fixed; therefore the relative order of the output wire that eventually carries (x) and the output wire that eventually carries (y_j) is independent of their actual values. Choose a zero‑one input where (x=0) and (y_j=1) (e.g., take (k=j-1) so that (y_1=\cdots=y_{j-1}=0) and (y_j=\cdots=y_n=1)). The correct merged sequence must place the (0) from (x) before the (1) from (y_j). Now choose an input where (x=1) and (y_j=0) (e.g., (k=j)); the correct sequence must place the (1) from (x) after the (0) from (y_j). Because the network fixes the relative order of these two wires, it cannot be correct for both cases. Hence every (y) must interact with (x).

Conclusion

All (n) elements (y_1,\dots,y_n) must be among the inputs that interact with (x). Therefore (n \le 2^D - 1), which is equivalent to [ D \ge \lceil \lg(n+1) \rceil. ]

This completes the proof. ∎