TAOCP 5.3.4 Exercise 11

We prove that Batcher's bitonic sorter of order \(2^t\) sorts not only bitonic sequences \(z_0\ge\cdots\ge z_k\le\cdots\le z_{2^t-1}\) but also reverse bitonic sequences \(z_0\le\cdots\le z_k\ge\cdots...

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.3.4: Networks for Sorting

Exercise 11. [M23] Prove that Batcher's bitonic sorter of order $2^t$ will not only sort sequences $\langle z_0, z_1, \ldots, z_{2^t-1}\rangle$ for which $z_0 \ge \cdots \ge z_k \le \cdots \le z_{2^t-1}$, it also will sort any sequence for which $z_0 \le \cdots \le z_k \ge \cdots \ge z_{2^t-1}$. [As a consequence, the network in Fig. 56 will sort 16 elements, since each stage consists of bitonic sorters or reverse-order bitonic sorters, applied to sequences that have been sorted in opposite directions.]

Verified: no
Solve time: 6m25s

Solution

We prove that Batcher's bitonic sorter of order (2^t) sorts not only bitonic sequences (z_0\ge\cdots\ge z_k\le\cdots\le z_{2^t-1}) but also reverse bitonic sequences (z_0\le\cdots\le z_k\ge\cdots\ge z_{2^t-1}).

By the zero‑one principle (stated in the text), it suffices to consider sequences of (0)s and (1)s. A (0)‑(1) sequence is bitonic iff it has the form (1^a0^b1^c) ((a,b,c\ge 0,;a+b+c=2^t)); it is reverse bitonic iff it has the form (0^a1^b0^c).

We first define the networks used.

Bitonic merge (M_t) (sorts a bitonic sequence of length (2^t) into ascending order):

  • (M_0): no comparators (1 element).
  • (M_1): a single comparator ((0,1)).
  • For (t\ge 2): (M_t) consists of
    1. comparators ((i,;i+2^{t-1})) for (i=0,\dots,2^{t-1}-1);
    2. (M_{t-1}) on lines (0,\dots,2^{t-1}-1);
    3. (M_{t-1}) on lines (2^{t-1},\dots,2^t-1).

Bitonic sorter (B_t) (sorts (2^t) elements into ascending order):

  • (B_0): no comparators.
  • (B_1 = M_1).
  • For (t\ge 2): (B_t) consists of
    1. (B_{t-1}) on the first half (lines (0,\dots,2^{t-1}-1)) - sorts ascending;
    2. (\operatorname{Rev}(B_{t-1})) on the second half (lines (2^{t-1},\dots,2^t-1)) - this is (B_{t-1}) with the order of lines reversed, which sorts descending;
    3. (M_t) on all (2^t) lines.

Lemma

For every (t\ge 0), the bitonic merge (M_t) transforms every (0)‑(1) sequence of the form (1^a0^b1^c) or (0^a1^b0^c) into the sorted sequence (0^{a+b+c}1^{\dots}) (all (0)s followed by all (1)s).

Proof. By induction on (t).

Base (t=0,1). (M_0) is trivial. (M_1) is a single comparator; all four (0)‑(1) sequences of length (2) are of both forms and are sorted.

Inductive step (t\ge 2). Assume the lemma holds for (t-1). Let (x) be a (0)‑(1) sequence of length (2^t) of the form (0^a1^b0^c) (the case (1^a0^b1^c) is symmetric). The first stage of (M_t) compares (x_i) with (x_{i+2^{t-1}}) for (i=0,\dots,2^{t-1}-1). Write (h=2^{t-1}). For (0)-(1) values (\min = \land) and (\max = \lor). Let [ y_i = x_i \land x_{i+h},\qquad z_i = x_i \lor x_{i+h}\qquad(i=0,\dots,h-1). ] The first half becomes (y=(y_0,\dots,y_{h-1})), the second half becomes (z=(z_0,\dots,z_{h-1})); then (M_{t-1}) is applied to (y) and to (z).

The sequence (x) consists of three blocks: (0^a), (1^b), (0^c). We analyse (y) and (z) by considering how the block of (1)s intersects the two halves ([0,h-1]) and ([h,2h-1]).

  • Case 1: The block of (1)s lies completely in one half.
    Then one half is all (0)s, the other half is a sequence of the form (0^*1^0^) (or monotone).
    Consequently (y) is all (0)s and (z) is exactly that half, which is reverse bitonic (or monotone).

  • Case 2: The block of (1)s spans both halves.
    Write the indices of the (1)s as ([a, a+b-1]). The left half (L) contains (1)s on ([a,h-1]) (if (a<h)); the right half (R) contains (1)s on ([0, a+b-1-h]) (if (a+b-1\ge h)).
    Then (y_i = 1) exactly when (i) belongs to the intersection ([a,h-1]\cap[0,a+b-1-h]). This intersection is non‑empty iff (b>h); in that case (y) is (0^*1^0^) (reverse bitonic), otherwise (y) is all (0)s.
    The sequence (z_i = 1) exactly on the union of the two intervals. If (b>h) the union is ([0,h-1]) (all (1)s); if (b\le h) the union is two disjoint intervals, so (z) is (1^*0^1^) (bitonic).

In every subcase (y) is either all (0)s or a reverse bitonic sequence, and (z) is either all (1)s or a bitonic sequence. By the induction hypothesis, (M_{t-1}) sorts (y) and (z) into non‑decreasing order. Hence (M_t(x)) is sorted. The symmetric argument (or complementation of bits) handles the form (1^a0^b1^c). ∎

Theorem

For every (t\ge 0), the bitonic sorter (B_t) sorts every bitonic sequence and every reverse bitonic sequence into non‑decreasing order.

Proof. By induction on (t).

Base (t=0,1). Trivial for (t=0). For (t=1), (B_1=M_1) sorts all sequences of length (2).

Inductive step (t\ge 2). Assume the theorem holds for (t-1). Let (x) be a reverse bitonic sequence of length (2^t) (the bitonic case is completely analogous). Write (x) as (0^a1^b0^c) in the (0)‑(1) case; the general case follows by the zero‑one principle.

The first part of (B_t) applies (B_{t-1}) to the first half (x[0\dots h-1]) and (\operatorname{Rev}(B_{t-1})) to the second half (x[h\dots 2h-1]) ((h=2^{t-1})).

  • The first half is a prefix of a reverse bitonic sequence. Any such prefix is either monotone or has the form (0^*1^0^) or (1^0^) - in all cases it is bitonic or reverse bitonic. By induction, (B_{t-1}) sorts it into ascending order.
  • The second half is a suffix of a reverse bitonic sequence. Reversing it yields a prefix of a reverse bitonic sequence, hence again bitonic or reverse bitonic. By induction, (B_{t-1}) sorts this reversed sequence ascending; therefore (\operatorname{Rev}(B_{t-1})) sorts the original second half into descending order.

After these two steps the whole sequence is ascending on the first half and descending on the second half - i.e. it is a reverse bitonic sequence. The final stage applies (M_t), which by the Lemma sorts reverse bitonic sequences into ascending order. Thus (B_t(x)) is sorted.

If the input is bitonic ((1^a0^b1^c)), the first half is a prefix of a bitonic sequence (again bitonic or reverse bitonic), the second half reversed is also bitonic or reverse bitonic, so both halves are sorted ascending and descending respectively. The concatenation is once more reverse bitonic, and (M_t) sorts it. ∎

This completes the proof. ∎

Notes

The zero‑one principle reduces the problem to (0)‑(1) sequences, where the two types of bitonic sequences become exactly (1^a0^b1^c) and (0^a1^b0^c). The inductive analysis of the bitonic merge (M_t) shows that the first stage splits any such sequence into a “min” half that is either all (0)s or reverse bitonic and a “max” half that is either all (1)s or bitonic; the recursive merges then finish the sorting. The bitonic sorter (B_t) uses two recursive sorters (one ascending, one descending) to turn any bitonic or reverse bitonic input into a reverse bitonic sequence, after which (M_t) completes the sort. The symmetry between the two types is reflected in the fact that the concatenation of an ascending and a descending sequence is always reverse bitonic.