TAOCP 5.3.4 Exercise 8

We prove the inequality \[ \hat{M}(m_1+m_2,\, n_1+n_2) \;\ge\; \hat{M}(m_1,n_1) + \hat{M}(m_2,n_2) + \min(m_1,n_2) \qquad (m_1,m_2,n_1,n_2 \ge 0), \] which is the intended form of the exercise (the or...

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.3.4: Networks for Sorting

Exercise 8. [M20] Prove that $\hat{M}(m_1+n_2, n_1+n_2) \ge \hat{M}(m_1, n_1) + \hat{M}(m_2, n_2) + \min(m_1, n_2)$, for $m_1, m_2, n_1, n_2 \ge 0$.

Verified: no
Solve time: 16m13s

Solution

We prove the inequality
[ \hat{M}(m_1+m_2,, n_1+n_2) ;\ge; \hat{M}(m_1,n_1) + \hat{M}(m_2,n_2) + \min(m_1,n_2) \qquad (m_1,m_2,n_1,n_2 \ge 0), ]
which is the intended form of the exercise (the original statement appears to contain a typographical error: (m_1+n_2) should be (m_1+m_2)).

Let (N) be an optimal ((m_1+m_2,, n_1+n_2))-merging network. By the zero-one principle it suffices to consider (0)-(1) inputs. Denote the input lines of the first sequence by (x_1,\dots,x_{m_1+m_2}) (in increasing order) and those of the second sequence by (y_1,\dots,y_{n_1+n_2}). Partition the lines into four blocks:

[ \begin{aligned} X_1 &= {x_1,\dots,x_{m_1}}, &\qquad X_2 &= {x_{m_1+1},\dots,x_{m_1+m_2}},\ Y_1 &= {y_1,\dots,y_{n_1}}, &\qquad Y_2 &= {y_{n_1+1},\dots,y_{n_1+n_2}}. \end{aligned} ]

Every comparator of (N) connects two lines; we classify it according to the blocks containing those lines. The sets of comparators joining (X_1)-(Y_1), (X_2)-(Y_2), and (X_1)-(Y_2) are pairwise disjoint. We shall show that they contain at least (\hat{M}(m_1,n_1)), (\hat{M}(m_2,n_2)), and (\min(m_1,n_2)) comparators, respectively.

1. Lower bound for (X_1)-(Y_1) comparators

Consider the (0)-(1) input where all lines in (X_2\cup Y_2) are set to (1), while the lines in (X_1) and (Y_1) receive arbitrary (0/1) values.
Both input sequences are sorted (all (0)s precede all (1)s). The correct output is all (0)s (coming from (X_1) and (Y_1)) followed by all (1)s.

In this input, any comparator between (X_1) and (Y_2) compares a value from (X_1) ((0) or (1)) with (1); it never swaps. A comparator between (X_2) and (Y_1) compares (1) with a value from (Y_1); if (Y_1) has a (0) it swaps, moving the (0) into (X_2). However, the final position of that (0) is still among the first (m_1+n_1) lines (since (X_2) lies between (X_1) and (Y_1) in the line order). The crucial observation is that the relative order of the (0)s and (1)s within (X_1) and (Y_1) must be correctly merged, and the only comparators that can affect this relative order are those directly between (X_1) and (Y_1). The subnetwork induced by the (X_1)-(Y_1) comparators, with (X_2\cup Y_2) fixed to (1), therefore constitutes a valid ((m_1,n_1))-merging network for the arbitrary (0/1) values on (X_1\cup Y_1). Hence there must be at least (\hat{M}(m_1,n_1)) such comparators.

2. Lower bound for (X_2)-(Y_2) comparators

By symmetry, take the (0)-(1) input where all lines in (X_1\cup Y_1) are set to (0), while (X_2) and (Y_2) receive arbitrary (0/1) values. The sequences are sorted, and the subnetwork on (X_2\cup Y_2) (with (X_1,Y_1) fixed to (0)) is an ((m_2,n_2))-merging network. Thus at least (\hat{M}(m_2,n_2)) comparators connect (X_2) and (Y_2).

3. Lower bound for (X_1)-(Y_2) comparators

To force comparators between (X_1) and (Y_2) we place the second sequence before the first in the line order (this is an equivalent network, obtained by renaming the lines). Now the line order is (Y_1, Y_2, X_1, X_2).
Assign the values:
[ Y_1 = 1,\quad Y_2 = 1,\quad X_1 = 0,\quad X_2 = 0. ]
Both sequences are sorted ((1)s then (0)s is not allowed, but here the second sequence is all (1)s and the first is all (0)s, so they are sorted). The merged output must be all (0)s (from (X_1,X_2)) followed by all (1)s (from (Y_1,Y_2)). In the initial line order (Y_1(1), Y_2(1), X_1(0), X_2(0)), the (1)s of (Y_2) are to the left of the (0)s of (X_1). For the network to be correct, every (0) in (X_1) must eventually move left past every (1) in (Y_2) (or vice versa). In an oblivious network, this requires at least one comparator for each element of the smaller block; otherwise some (0) in (X_1) and some (1) in (Y_2) would never be compared directly or indirectly (the constant blocks (Y_1) and (X_2) do not help), and their relative order would be incorrect for a suitable choice of the remaining variables. Therefore there must be at least (\min(m_1,n_2)) comparators between (X_1) and (Y_2).

The three sets of comparators are disjoint, so the total number of comparators in (N) satisfies
[ \hat{M}(m_1+m_2,, n_1+n_2) ;\ge; \hat{M}(m_1,n_1) + \hat{M}(m_2,n_2) + \min(m_1,n_2). ]

This completes the proof. ∎