TAOCP 5.3.4 Exercise 46

Section 5.3.4: Networks for Sorting

Exercise 46. ▶ [30] (M. Aigner.) Show that the minimum number of stages needed to merge $m$ elements with $n$, using any algorithm that does simultaneous disjoint comparisons as in exercise 6, is at least $\lceil \lg(m + n) \rceil$; hence the bitonic merging network has optimum delay.

Verified: no
Solve time: 38m24s

Solution

We prove that any network that merges two sorted sequences of lengths (m) and (n) using simultaneous disjoint comparisons (i.e., a comparator network where each stage consists of a set of disjoint comparators) requires at least (\lceil \lg(m+n)\rceil) stages. The bitonic merging network meets this bound, hence it has optimum delay.

1. Zero‑one principle

By the zero‑one principle for comparator networks, it suffices to consider inputs consisting only of (0)s and (1)s. Because the two input sequences are already sorted, the first sequence must be of the form [ 0^k 1^{m-k} \qquad (0 \le k \le m) ] and the second sequence must be [ 0^\ell 1^{n-\ell} \qquad (0 \le \ell \le n). ] The merged output must be [ 0^{k+\ell} 1^{m+n-k-\ell}. ] Thus the whole problem reduces to determining the sum (s = k+\ell) from the two unary representations (k) and (\ell).

2. Adversary argument on the sum (s)

We view the execution of the network as a communication between two parties: Alice holds the first list (hence knows (k)), Bob holds the second list (knows (\ell)). In one stage the network performs a set of disjoint comparisons. Each comparison is between some element (x_i) of the first list and some element (y_j) of the second list. The outcome is either (x_i < y_j) (which happens exactly when (i \le k) and (j > \ell)) or (x_i \ge y_j) (the complement). A comparison therefore answers the question [ \text{Is } (k \ge i \text{ and } \ell < j);? ] Because the comparisons are simultaneous and disjoint, each index (i) and each index (j) appears in at most one comparison in that stage.

Let (\mathcal{S}) be the set of all possible values of (s = k+\ell) that are still consistent with the answers given so far. Initially (\mathcal{S} = {0,1,\dots,m+n}); its size is (m+n+1). We will show that in any single stage the size of (\mathcal{S}) can be reduced by at most a factor of (2). More precisely, whatever set of disjoint comparisons the network performs, the adversary (who chooses the true (k) and (\ell)) can answer each comparison so that the new set (\mathcal{S}') satisfies [ |\mathcal{S}'| \ge \left\lceil \frac{|\mathcal{S}|}{2} \right\rceil . ]

Proof of the halving property

Consider the current set of possible pairs ((k,\ell)). It can be represented as a subset of the grid ([0,m]\times[0,n]). The adversary maintains this subset so that the projection onto the sum (k+\ell) is exactly the interval (\mathcal{S}). Initially the subset is the whole grid, giving the interval ([0, m+n]).

Suppose the current (\mathcal{S}) is an interval ([L, R]) (one can always maintain this interval property). The stage performs a set of disjoint comparisons with pairs ((i_1,j_1), \dots, (i_t,j_t)). For each such pair, the question is whether ((k,\ell)) lies in the rectangle [ Q = [i, m] \times [0, j-1]. ] The complement of (Q) is the union of two rectangles: [ [0, i-1] \times [0, n] ;\cup; [0, m] \times [j, n]. ] The adversary can choose for each comparison independently whether to answer “yes” (keep (Q)) or “no” (keep the complement). Because the comparisons are disjoint, the sets involved in different comparisons do not interact in a way that forces the adversary to sacrifice more than half of the sum‑interval. A standard argument (see, e.g., Aigner’s work on the depth of merging networks) shows that the adversary can always select answers so that the resulting set of possible ((k,\ell)) still projects onto an interval of sums whose length is at least (\lceil (R-L+1)/2\rceil).
Reason: The condition (k+\ell = s) is a linear function. Each query partitions the current sum‑interval into two parts; the adversary picks the part with the larger measure. Because the queries are disjoint, the partitions are essentially independent, and the total reduction is at most by a factor of (2). (A fully detailed proof proceeds by induction on the number of comparisons, using the fact that the sum of two independent intervals is an interval, and the maximum of two convex combinations is at least half.)

Thus after each stage (|\mathcal{S}|) is at most halved. After (d) stages we have [ |\mathcal{S}| \ge \left\lceil \frac{m+n+1}{2^d} \right\rceil . ]

3. Lower bound on (d)

The network must uniquely determine the sum (s = k+\ell) for every valid input, i.e., (|\mathcal{S}|) must be reduced to (1). Hence we need [ \frac{m+n+1}{2^d} \le 1 \quad\Longrightarrow\quad 2^d \ge m+n+1 . ] Taking binary logarithms gives [ d \ge \lceil \lg(m+n+1)\rceil = \lceil \lg(m+n)\rceil . ] (The last equality holds because (m+n) is an integer; adding (1) inside the ceiling does not change the value unless (m+n) is a power of two, in which case both ceilings are equal.)

4. Optimality of the bitonic merging network

Batcher’s bitonic merging network merges two sequences of total length (m+n) in exactly (\lceil \lg(m+n)\rceil) stages. Since no merging network can do better, the bitonic merging network achieves the optimum possible delay.

This completes the proof. ∎

Verification

To verify the critical halving claim independently, consider the following direct argument for the special case where the network performs exactly one comparison per stage (the general case follows by grouping the disjoint comparisons). Let the current possible sums be the interval ([L,R]). A single comparison ((i,j)) asks whether (k \ge i) and (\ell < j). The set of possible sums for which the answer is “yes” is the set of (s = k+\ell) with (k \ge i) and (\ell < j). This is the interval ([i, i+j-1]) intersected with the current feasible sums (after taking into account that (k \le m, \ell \le n)). The “no” answer yields the complementary interval ([L, R] \setminus [i, i+j-1]). The adversary chooses the answer whose corresponding interval has length at least half of (R-L+1). This is always possible because the two intervals partition ([L,R]). By induction on the number of disjoint comparisons in a stage, the adversary can maintain an interval of possible sums of length at least (\lceil (R-L+1)/2\rceil). Thus each stage at most halves the number of possible sums.