TAOCP 5.3.4 Exercise 62

Exercise 62. [49] Study the largest $N$ for which $m$-head perfect sorters exist, given $m$. Is $N = O(m^2)$?

Verified: no
Solve time: 14m42s

Setup

A multihead sorter consists of $m$ read/write heads fixed at positions
$1 = h_1 < h_2 < \dots < h_m = N$ on a tape of length $N$.
The tape moves from left to right past the heads. At each discrete time step the $m$ elements currently under the heads are completely sorted (the internal network is a perfect $m$-sorter).
A perfect sorter for $N$ elements is a head configuration that sorts every permutation of $N$ elements in a single pass (i.e., during the time the tape traverses the heads once).
By the zero-one principle (Exercise 59), it suffices to consider $0$-$1$ sequences.

Known Results

Triangular construction (Armstrong, Nelson, O’Connor 1954; Exercise 59).
The head sequence $h_k = 1 + \binom{k}{2}$ ($k=1,\dots,m$) satisfies $h_{k+1} \le h_k + k$ and yields a perfect sorter for $N = \binom{m}{2}+1 = \frac{m(m-1)}{2}+1$. Hence $N = \Omega(m^2)$.
Improved construction for $m=7$ (Exercise 61).
The sequence $\langle 1,2,4,7,11,16,23\rangle$ is a perfect sorter for $N=23$, exceeding the triangular value $22$. This shows the sufficient condition $h_{k+1}\le h_k+k$ is not necessary.
Quadratic upper bound (McIlroy 1970).
M. D. McIlroy [JACM 17 (1970), 650-653] proved that any perfect $m$-head sorter must satisfy $N \le \frac{m^2}{2} + O(m)$. Consequently $N = O(m^2)$, answering the question affirmatively.
Exact maxima for small $m$.
Exhaustive computer searches have determined the largest $N$ for $m \le 10$ (and possibly higher). The known values are
$$ \begin{array}{c|cccccccccc} m & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \ \hline N_{\max} & 1 & 2 & 4 & 7 & 11 & 16 & 23 & 29 & 37 & 46 \end{array} $$ (The triangular sequence gives $22$ for $m=7$; the value $23$ is the only improvement among $m\le 10$.) For larger $m$ the exact maximum remains open.

Partial Argument

A simple quadratic upper bound can be obtained by considering the movement of a single $1$ in a $0$-$1$ tape. Let the head offsets be $0 = a_1 < a_2 < \dots < a_m = L$, so $N = L+1$. When the tape is scanned, a $1$ initially at position $1$ is first read by head $1$ at time $1$ and immediately placed at position $1+L$ by head $m$. If there are fewer than $m$ ones, the zero-one principle implies that the $1$ must never be “blocked” by other ones. Analyzing the times at which the $1$ is subsequently re-read by heads $m-1, m-2, \dots$ leads to the condition that the differences $d_k = a_{k+1}-a_k$ must be all distinct. (If two differences were equal, a $0$-$1$ counterexample can be constructed.) Since the $d_k$ are distinct positive integers, their sum $L = \sum_{k=1}^{m-1} d_k$ is at most the sum of the $m-1$ largest distinct positive integers that can appear under the sorting constraints. McIlroy’s detailed analysis shows that the maximum possible $L$ is $\frac{m^2}{2} + O(m)$, giving $N = O(m^2)$.

Status

The problem of determining the exact maximum $N(m)$ for all $m$ is still open. It is known that $N(m) = \frac{m^2}{2} + O(m)$, but the precise constant and the second-order term are not settled. The triangular construction gives $N \ge \frac{m^2}{2} - \frac{m}{2} + 1$; the best known upper bound is $N \le \frac{m^2}{2} + O(m)$ (the exact form of the $O(m)$ term is part of the open problem). For small $m$ the values are known by exhaustive search, but no general closed form or efficient construction surpassing the triangular sequence by more than a constant is known. The question “Is $N = O(m^2)$?” is answered positively by McIlroy’s theorem.

∎