\magnification 1200\nopagenumbers\noindent
{\bf Edward A. Bender and S. Gill Williamson}\medskip\noindent
{\bf Periodic Sorting Using Minimum Delay, Recursively Constructed Merging Networks}
\vskip.5cm\noindent Let $\alpha$ and $\beta$ be a partition of $\{1,\ldots,n\}$
into two blocks.
A merging network is a network of comparators which allows as input
arbitrary real numbers and has the property that, whenever the input
sequence $x_1,x_2,\ldots,x_n$ is such that the subsequence in the
positions $\alpha$ and the subsequence in the positions $\beta$ are
each sorted, the output sequence will be sorted. 
We study the class of ``recursively constructed'' merging networks and
characterize those with delay $\lceil\log_2 n\rceil$ (the best possible
delay for all merging networks).
When $n$ is a power of 2, we show that at least $3^{n/2-1}$ of these
nets are log-periodic sorters; that is, they sort any input sequence
after $\log_2n$ passes through the net. 
(Two of these have appeared previously in the literature.)

\end