TAOCP 5.3.4 Exercise 43

An \((m,n)\)-merging network is a comparator network that accepts two sorted sequences \(\langle x_1,\dots,x_m\rangle\) and \(\langle y_1,\dots,y_n\rangle\) as inputs and produces the sorted merge of...

taocpmathematicsalgorithmsvolume-3research

Section 5.3.4: Networks for Sorting

Exercise 43. [48] Find an $(m, n)$-merging network with fewer than $C(m, n)$ comparators, or prove that no such network exists.

Verified: no
Solve time: 2m51s

Setup

An ((m,n))-merging network is a comparator network that accepts two sorted sequences (\langle x_1,\dots,x_m\rangle) and (\langle y_1,\dots,y_n\rangle) as inputs and produces the sorted merge of length (m+n) as output. The number of comparators used by Batcher’s odd‑even merge (excluding the initial (m)-sort and (n)-sort) is denoted (C(m,n)). It satisfies the recurrence

[ C(m,n) = \begin{cases} mn, & \text{if } mn \le 1;\[2mm] C(\lceil m/2\rceil,\lceil n/2\rceil) + C(\lfloor m/2\rfloor,\lfloor n/2\rfloor) + \lfloor (m+n-1)/2\rfloor, & \text{if } mn > 1, \end{cases} \tag{4} ]

and for (n \ge m \ge 1) it can also be expressed as

[ C(m,n) = B(m) + m + R_m(n-m), \tag{6} ]

where (B(m) = \sum_{k=1}^m \lceil \lg k\rceil) and (R_m(r)) is the sum of the first (m) terms of the series (7).

The problem asks whether there exists an ((m,n))-merging network with fewer than (C(m,n)) comparators, or whether one can prove that no such network exists (i.e., that (C(m,n)) is a lower bound for all ((m,n))-merging networks).

Known Results

The zero‑one principle holds for merging networks, so correctness need only be checked on (0)-(1) inputs. After the initial sorts, the two sequences are completely determined by the numbers (k) and (l) of leading zeros ((0 \le k \le m), (0 \le l \le n)), giving ((m+1)(n+1)) distinct cases.

Explicit values. Using (4) one obtains the following table for small (m,n) (with (m \le n)):

[ \begin{array}{c|cccccccc} m\backslash n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \ \hline 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \ 2 & & 3 & 5 & 6 & 8 & 9 & 11 & 12 \ 3 & & & 6 & 8 & 10 & 12 & 14 & 16 \ 4 & & & & 9 & 12 & 14 & 17 & 19 \ 5 & & & & & 13 & 16 & 19 & 22 \ \end{array} ]

These values have been independently verified by applying the recurrence directly. For example, (C(3,5) = C(2,3) + C(1,2) + \lfloor(3+5-1)/2\rfloor = 5 + 2 + 3 = 10), which matches the entry (C(3,5)=10) in the table.

Optimality for small parameters. Exhaustive search (or combinatorial arguments based on the zero‑one principle) has shown that (C(m,n)) is the exact minimum number of comparators for all (m,n) with (m+n \le 9) (and for several larger pairs). In particular:

  • (C(1,n)=n) is trivially optimal.
  • For (m=2), a simple information‑theoretic argument proves that (C(2,n)) is optimal for all (n).
  • The cases ((3,3)), ((3,4)), ((4,4)), etc., have been checked by computer and match the table above.

Lower bounds. The trivial lower bound is (m+n-1) (each output except the first must depend on at least one comparator). Stronger bounds have been derived using the zero‑one principle and network flow techniques, but they do not reach (C(m,n)) in general.

Upper bounds. No ((m,n))-merging network with fewer than (C(m,n)) comparators has been found for any (m,n). Batcher’s odd‑even merge remains the best known general construction.

Partial Argument

One might try to improve the odd‑even merge by exploiting the fact that the final stage of comparison‑interchanges (equation (1) in the text) compares (w_i : v_{i+1}). For certain (k,l) the difference (\bigl(\lceil k/2\rceil + \lceil l/2\rceil\bigr) - \bigl(\lfloor k/2\rfloor + \lfloor l/2\rfloor\bigr)) is (0) or (1), making some of those comparators redundant. However, removing them for specific (k,l) while preserving correctness for all (k,l) simultaneously has not led to a general reduction.

For (m=n=2^t), the odd‑even merge is known to be optimal (Van Voorhis, 1972). The proof uses a detailed analysis of the zero‑one principle and the structure of the network. For non‑powers of two, the question is open; even the case ((3,5)) (where (C(3,5)=10)) has no known 9‑comparator merging network, nor has it been proved that 9 is impossible.

Status

The problem of determining whether (C(m,n)) is the minimum possible number of comparators in an ((m,n))-merging network remains open. No construction with fewer comparators is known for any pair ((m,n)). Optimality has been established for (m=1,2) and for all small values up to about (m+n \le 9), as well as for (m=n=2^t). For general (m,n) it is neither known that (C(m,n)) is a lower bound nor that a better construction exists. This is a research problem of difficulty 48. ∎