TAOCP 5.3.4 Exercise 10

We first recall the definitions of Batcher's bitonic sorter and the bitonic merger from the remarks preceding equation (15).

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.3.4: Networks for Sorting

Exercise 10. [M22] Prove that Batcher's bitonic sorter, as defined in the remarks preceding (15), is valid. [Hint: It is only necessary to prove that all sequences consisting of $k$ 1s followed by $l$ 0s followed by $n - k - l$ 1s will be sorted.]

Verified: no
Solve time: 15m

Solution

We first recall the definitions of Batcher's bitonic sorter and the bitonic merger from the remarks preceding equation (15). All sequences have length a power of 2.

  • Bitonic merger (M(n)): A network that takes a bitonic sequence and sorts it into non‑decreasing order.
    (M(1)) is trivial. For (n>1), (M(n)) consists of the comparators
    ((1 : 1+n/2),;(2 : 2+n/2),;\ldots,;(n/2 : n))
    followed by two copies of (M(n/2)) applied to the first and second halves.

  • Bitonic sorter (S(n)): A network that sorts an arbitrary sequence into non‑decreasing order.
    (S(1)) is trivial. For (n>1), (S(n)) consists of

    • (S(n/2)) on the first half with all comparator directions reversed (i.e. sorting into non‑increasing order),
    • (S(n/2)) on the second half (sorting into non‑decreasing order),
    • (M(n)) on the whole sequence.

We must prove that (S(n)) is a valid sorting network. By the zero-one principle (Section 5.3.4) it suffices to show that (S(n)) correctly sorts every sequence of (0)s and (1)s.

Proof by induction on (n).
The case (n=1) is trivial. Assume (n>1) and that (S(n/2)) correctly sorts every (0)‑(1) sequence into non‑decreasing order (and, by reversing all comparators, also into non‑increasing order). Let (X) be an arbitrary (0)‑(1) sequence of length (n). After the two half‑sorters the first half is non‑increasing, hence of the form (1^a0^b), and the second half is non‑decreasing, hence of the form (0^c1^d). Their concatenation is
[ 1^a0^b0^c1^d = 1^a0^{b+c}1^d , ] which is exactly a sequence of the form (1^k0^l1^{n-k-l}) (with (k=a,;l=b+c,;n-k-l=d)). The network then applies (M(n)) to this sequence. Therefore the whole proof reduces to the following lemma.

Lemma. For every (n) (a power of 2) the bitonic merger (M(n)) sorts every (0)‑(1) sequence of the form (1^k0^l1^{n-k-l}) into non‑decreasing order.

Proof of the Lemma. We proceed by induction on (n). The base (n=2) is checked directly: the possible sequences (00,;01,;10,;11) are all of the required form (with (k,l\ge0,;k+l\le2)) and the single comparator ((1:2)) sorts them correctly.

Now assume (n>2) and that the lemma holds for (n/2). Let (X = 1^k0^l1^{n-k-l}) be given. Write (m=n/2) and split (X) into its first half (H_1 = (x_1,\ldots,x_m)) and second half (H_2 = (x_{m+1},\ldots,x_n)). The first stage of (M(n)) consists of the comparators ((i : i+m)) for (i=1,\ldots,m). For (0)‑(1) inputs this computes [ y_i = \min(H_1[i],H_2[i]), \qquad z_i = \max(H_1[i],H_2[i]) \qquad (i=1,\ldots,m). ] Let (Y = (y_1,\ldots,y_m)) and (Z = (z_1,\ldots,z_m)). We will show:

  1. (Y) and (Z) are bitonic (0)‑(1) sequences (i.e. each is of the form (1^p0^q1^r) or (0^p1^q0^r), or monotone).
  2. (\max(Y) \le \min(Z)).

Once these are established, the induction hypothesis applied to (M(m)) guarantees that the recursive calls sort (Y) and (Z) into non‑decreasing order. Because every element of the sorted (Y) is (\le) every element of the sorted (Z), their concatenation is fully sorted, completing the induction step.

Proof of (1). The original sequence (X) has at most two transitions between (0) and (1). The halves (H_1,H_2) are contiguous segments of (X), so each is itself a bitonic (0)‑(1) sequence (of length (m)). The operations (y_i = H_1[i] \wedge H_2[i]) and (z_i = H_1[i] \vee H_2[i]) are elementwise AND and OR. It is easy to verify that the AND and OR of two bitonic (0)‑(1) sequences are again bitonic (a short case analysis on the relative positions of the transitions shows that the number of transitions never exceeds two). Hence (Y) and (Z) are bitonic.

Proof of (2). We must show that there is no pair ((i,j)) with (y_i=1) and (z_j=0). If (y_i=1) then (H_1[i]=H_2[i]=1). If (z_j=0) then (H_1[j]=H_2[j]=0). We prove that such (i,j) cannot coexist for (X = 1^k0^l1^{n-k-l}).

The sequence (X) consists of a block of (k) ones, then (l) zeros, then (n-k-l) ones. Consider the two absolute positions corresponding to a relative index (i): they are (i) and (i+m). The condition (H_1[i]=H_2[i]=1) means both (x_i=1) and (x_{i+m}=1). Since the zeros of (X) form a single contiguous block of length (l), the interval ([i,,i+m]) of length (m) contains no zero. Therefore the zero block lies entirely outside this interval. There are three possibilities:

  • The zero block is entirely before (i). Then all elements of (H_2) (which start at (m+1 \ge i+m)) are ones, so (H_2) has no zero; consequently there is no (j) with (H_1[j]=H_2[j]=0).
  • The zero block is entirely after (i+m). Then all elements of (H_1) (which end at (m \le i+m)) are ones, so (H_1) has no zero; again no (j) with both zeros.
  • The zero block lies strictly between (i) and (i+m). Then (H_1) has ones up to some point and zeros afterwards, while (H_2) has zeros at the beginning and ones afterwards. A careful look at the relative indices shows that the zeros of (H_1) occur at relative indices (> i), whereas the zeros of (H_2) occur at relative indices (< i). Hence there is no relative index where both halves have zero.

In all cases we cannot have simultaneously a position with (y_i=1) and a position with (z_j=0). Thus (\max(Y)\le\min(Z)). ∎

Remark on the other bitonic form. The bitonic (0)‑(1) sequences are exactly those of the form (1^k0^l1^{n-k-l}) or (0^k1^l0^{n-k-l}) (including monotone sequences). The hint tells us that it is enough to prove the lemma for the first form. The second form follows by a completely analogous case analysis, or by noting the symmetry of the network: complementing all inputs and outputs of (M(n)) and reversing the order of the lines transforms the network into itself, while mapping the first form to the second and reversing the sorted order; a second reversal restores the desired order. We omit the straightforward details.

Finally, the induction on (S(n)) is complete: the half‑sorters produce a sequence of the form (1^k0^l1^{n-k-l}), and the lemma guarantees that (M(n)) sorts it correctly. Hence (S(n)) is a valid sorting network for all (n) (powers of 2). For arbitrary (n) one pads with dummy elements; the standard argument extends the result. This completes the proof. ∎