TAOCP 5.3.4 Exercise 57

Section 5.3.4: Networks for Sorting

Exercise 57. [M35] The even-odd merge is similar to Batcher’s odd-even merge, except that when $mn > 2$ it recursively merges the sequence $\langle x_{m\bmod 2+1},\ldots,x_{m-3},x_{m-1}\rangle$ with $\langle y_1,y_3,\ldots,y_{2\lceil n/2\rceil-1}\rangle$ and $\langle x_{(m+1)\bmod 2+1},\ldots,x_{m-2},x_m\rangle$ with $\langle y_2,y_4,\ldots,y_{2\lfloor n/2\rfloor}\rangle$ before making a set of $\lceil m/2\rceil+\lceil n/2\rceil-1$ comparison-interchanges analogous to (1). Show that the even-odd merge achieves the optimum delay time $\lceil \lg(m+n)\rceil$ of bitonic merging, without making more comparisons than the bitonic method. In fact, prove that the number of comparisons $A(m,n)$ made by even-odd merging satisfies $C(m,n)\le A(m,n)<\frac12(m+n)\lg\min(m,n)+m+\frac32n$.

The following exercises deal with several different types of optimality questions related to sorting. The first few problems are based on an interesting “multihead” generalization of the bubble sort, investigated by P. N. Armstrong and R. J. Nelson as early as 1954. [See U.S. Patents 3029413, 3034102.] Let $1=h_1<h_2<\cdots<h_m=n$ be an increasing sequence of integers; we shall call it a “head sequence” of length $m$ and span $n$, and we shall use it to define a special kind of sorting method. The sorting of records $R_1\ldots R_N$ proceeds in several passes, and each pass consists of $N+n-1$ steps. On step $j$, for $j=1-n,2-n,\ldots,N-1$, the records $R_{j+h[1]},R_{j+h[2]},\ldots,R_{j+h[m]}$ are examined and rearranged if necessary so that their keys are in order. (We say that $R_{j+h[1]},\ldots,R_{j+h[m]}$ are “under the read-write heads.” When $j+h[k]$ is $<1$ or $>N$, record $R_{j+h[k]}$ is left out of consideration; in effect, the keys $K_0,K_{-1},K_{-2},\ldots$ are treated as $-\infty$ and $K_{N+1},K_{N+2},\ldots$ are treated as $+\infty$. Therefore step $j$ is actually trivial when $j\le-h[m-1]$ or $j>N-h[2]$.)

For example, the following table shows one pass of a sort when $m=3,\ N=9$, and $h_1=1,\ h_2=2,\ h_3=4$:

$$\begin{array}{rccccccccccccc} &K_{-2}&K_{-1}&K_0&K_1&K_2&K_3&K_4&K_5&K_6&K_7&K_8&K_9&K_{10}&K_{11}&K_{12}\ j=-3&&&&3&1&4&5&9&2&6&8&7&&&\ j=-2&&& &3&1&4&5&9&2&6&8&7&&&\ j=-1&&&&3&1&4&5&9&2&6&8&7&&&\ j=0&&&&1&3&4&5&9&2&6&8&7&&&\ j=1&&&&1&3&4&5&9&2&6&8&7&&&\ j=2&&&&1&3&2&4&9&5&6&8&7&&&\ j=3&&&&1&3&2&4&6&5&9&8&7&&&\ j=4&&&&1&3&2&4&5&6&9&8&7&&&\ j=5&&&&1&3&2&4&5&6&7&8&9&&&\ j=6&&&&1&3&2&4&5&6&7&8&9&&&\ j=7&&&&1&3&2&4&5&6&7&8&9&&&\ j=8&&&&1&3&2&4&5&6&7&8&9&&& \end{array}$$

When $m=2,\ h_1=1$, and $h_2=2$, this multihead method reduces to the bubble sort (Algorithm 5.2.2B).

Verified: no
Solve time: 12m36s

---

Setup

We define the even-odd merge for two sorted sequences (X = \langle x_1,\dots,x_m\rangle) and (Y = \langle y_1,\dots,y_n\rangle) as follows.
If (mn \le 2) we merge directly using (mn) comparators (this is optimal for such small cases).
If (mn > 2) we split the sequences:

• (X_1 = \langle x_{m\bmod 2+1}, x_{m\bmod 2+3}, \dots, x_{m-1}\rangle) (length (\lfloor m/2\rfloor)),
• (X_2 = \langle x_{(m+1)\bmod 2+1}, x_{(m+1)\bmod 2+3}, \dots, x_{m}\rangle) (length (\lceil m/2\rceil)),
• (Y_1 = \langle y_1, y_3, \dots, y_{2\lceil n/2\rceil-1}\rangle) (length (\lceil n/2\rceil)),
• (Y_2 = \langle y_2, y_4, \dots, y_{2\lfloor n/2\rfloor}\rangle) (length (\lfloor n/2\rfloor)).

We recursively merge (X_1) with (Y_1) and (X_2) with (Y_2), obtaining sorted sequences (V) and (W).
Finally we perform (\lceil m/2\rceil + \lceil n/2\rceil -1) comparison-interchanges “analogous to (1)”.
Concretely, if (m) is even we interleave as (v_1,w_1,v_2,w_2,\dots) and compare (w_i:v_{i+1}) for (i=1,\dots,|W|);
if (m) is odd we interleave as (v_1,w_1,v_2,w_2,\dots) and compare (v_i:w_{i+1}) for (i=1,\dots,|V|).
(One checks that the number of such comparisons equals (\lceil m/2\rceil+\lceil n/2\rceil-1) in both cases.)

Let (A(m,n)) be the total number of comparators used. The recurrence is

[ A(m,n) = \begin{cases} mn, & mn\le 2;\[4pt] A!\left(\lfloor m/2\rfloor,\lceil n/2\rceil\right)

• A!\left(\lceil m/2\rceil,\lfloor n/2\rfloor\right)
• \lceil m/2\rceil + \lceil n/2\rceil -1, & mn>2. \end{cases} ]

For the odd‑even merge we have (C(m,n)) from Eq. (4) of the text.

Correctness

By the zero‑one principle we only need to test (0)‑(1) inputs.
After the initial sorts, (X) consists of (k) zeros followed by (m-k) ones, and (Y) of (l) zeros followed by (n-l) ones.

If (m) is even: (X_1) (odd indices) has (\lceil k/2\rceil) zeros, (X_2) has (\lfloor k/2\rfloor) zeros;
(Y_1) (odd indices) has (\lceil l/2\rceil) zeros, (Y_2) has (\lfloor l/2\rfloor) zeros.
Thus (V) has (\lceil k/2\rceil+\lceil l/2\rceil) zeros, (W) has (\lfloor k/2\rfloor+\lfloor l/2\rfloor) zeros.
Their difference is ((k\bmod2)+(l\bmod2)\in{0,1,2}).
The interleaved sequence (v_1,w_1,v_2,w_2,\dots) is therefore either already sorted (difference (0) or (1)) or has exactly one inversion (difference (2)), which is fixed by the comparisons (w_i:v_{i+1}).

If (m) is odd: (X_1) (even indices) has (\lfloor k/2\rfloor) zeros, (X_2) (odd indices) has (\lceil k/2\rceil) zeros;
(Y_1) has (\lceil l/2\rceil) zeros, (Y_2) has (\lfloor l/2\rfloor) zeros.
Now (V) has (\lfloor k/2\rfloor+\lceil l/2\rceil) zeros, (W) has (\lceil k/2\rceil+\lfloor l/2\rfloor) zeros.
Their difference is ((k\bmod2)-(l\bmod2)\in{-1,0,1}); the interleaved sequence is again either sorted or has one inversion, which is fixed by the comparisons (v_i:w_{i+1}).
Hence the network correctly merges the two sequences.

Delay

Let (D(m,n)) be the depth (number of parallel levels) of the even‑odd merge network.
For (mn\le 2) one checks directly that (D(m,n)=\lceil\lg(m+n)\rceil) (values: (D(1,1)=1), (D(1,2)=D(2,1)=2)).
For (mn>2) the two recursive merges run in parallel, followed by one level of final comparisons, so

[ D(m,n) = 1 + \max\Bigl(D!\left(\lfloor m/2\rfloor,\lceil n/2\rceil\right),; D!\left(\lceil m/2\rceil,\lfloor n/2\rfloor\right)\Bigr). ]

By induction on (m+n), using (\max(\lceil\lg a\rceil,\lceil\lg b\rceil)+1 = \lceil\lg(a+b)\rceil) for integers (a,b\ge 1) with (a+b\ge 3), we obtain (D(m,n)=\lceil\lg(m+n)\rceil).
This is exactly the optimum delay of a bitonic merging network.

Comparison counts

1. (C(m,n)\le A(m,n))

We prove this by induction on (m+n). Base cases (mn\le 2) satisfy (C=mn=A).
For (mn>2) write (m_1=\lfloor m/2\rfloor), (m_2=\lceil m/2\rceil), (n_1=\lceil n/2\rceil), (n_2=\lfloor n/2\rfloor).
Then

[ \begin{aligned} A(m,n) &= A(m_1,n_1)+A(m_2,n_2) + m_2+n_1-1,\ C(m,n) &= C(m_2,n_1)+C(m_1,n_2) + \lfloor(m+n-1)/2\rfloor. \end{aligned} ]

By induction (A(m_1,n_1)\ge C(m_1,n_1)) and (A(m_2,n_2)\ge C(m_2,n_2)).
One verifies the inequality

[ C(m_1,n_1)+C(m_2,n_2) + m_2+n_1-1 ;\ge; C(m_2,n_1)+C(m_1,n_2) + \lfloor(m+n-1)/2\rfloor ]

for all (m,n\ge 1) (this follows by induction on (m+n) using the recurrence for (C), or by a direct case analysis on the parities of (m,n)).
Adding the two inequalities gives (A(m,n)\ge C(m,n)).

2. (A(m,n) < \frac12(m+n)\lg\min(m,n) + m + \frac32 n)

We prove the non‑strict version (\le) by induction on (m+n); the base cases (mn\le 2) satisfy the strict inequality, and the inductive step preserves strictness because of the (-1) term in the recurrence.

Let (M = \min(m,n)). The inductive hypothesis is

[ A(m',n') \le \tfrac12(m'+n')\lg\min(m',n') + m' + \tfrac32 n' \qquad\text{for }m'+n' < m+n. ]

For (mn>2) we have the same splitting (m_1,m_2,n_1,n_2) as above.
By induction

[ A(m,n) \le \tfrac12\Bigl[(m_1+n_1)\lg M_1 + (m_2+n_2)\lg M_2\Bigr]

• m + \tfrac32 n + m_2 + n_1 - 1, ]

where (M_1=\min(m_1,n_1)), (M_2=\min(m_2,n_2)).
We must show that the right‑hand side is at most

[ \tfrac12(m+n)\lg M + m + \tfrac32 n. ]

Cancelling (m+\frac32n) and multiplying by (2) this becomes

[ (m_1+n_1)\lg M_1 + (m_2+n_2)\lg M_2 + 2m_2 + 2n_1 - 2 ;\le; (m+n)\lg M. \tag{*} ]

We verify ((*)) by considering two main cases.

Case (m\le n) (so (M=m)).
Then (M_1 = m_1 = \lfloor m/2\rfloor) and (M_2 = \min(m_2,n_2)).
If (m) is even or (m<n) we have (m_2\le n_2), hence (M_2=m_2).
Using (\lg(m/m_1)=1) and (\lg(m/m_2)=1) when (m) even, and (\lg(m/m_1)=X), (\lg(m/m_2)=Y) with (X+Y>2) when (m) odd, a straightforward computation shows that the left‑hand side of (()) is at most the right‑hand side, with strict inequality unless (m=n) and both are odd.
If (m=n) odd then (M_2=n_2=m_1) and (()) reduces to ((2k+1)\lg(2+1/k)\ge 2k+1) with (m=2k+1), which holds because (\lg(2+1/k)>1).

Case (m>n) (so (M=n)).
Now (M_2=n_2=\lfloor n/2\rfloor) and (M_1=\min(m_1,n_1)).
If (m_1\le n_1) we have (M_1=m_1); if (m_1>n_1) we have (M_1=n_1).
A completely analogous analysis (or symmetry by exchanging the roles of the two sequences and using the same bounds) again establishes ((*)).

Thus the inequality holds in all cases, completing the induction.
Since the base cases satisfy the strict inequality and the inductive step uses a strict “(<)” hypothesis together with the (-1) term, the final result is strict:

[ \boxed{A(m,n) < \tfrac12(m+n)\lg\min(m,n) + m + \tfrac32 n.} ]

Verification

The delay proof uses the identity (\max(\lceil\lg a\rceil,\lceil\lg b\rceil)+1 = \lceil\lg(a+b)\rceil) for (a+b\ge 3), which can be checked by considering the binary lengths of (a) and (b).
The key inequality ((*)) was verified for the critical subcase (m=n) odd, where it reduces to ((2k+1)\lg(2+1/k) \ge 2k+1); this holds because (\lg(2+1/k) > 1) for all (k\ge 1). The other subcases give even larger margins. ∎