Abstract of Paper

On Optimal Merging Networks
by Kazuyuki Amano and Akira Maruoka

Abstract:

We prove that Batcher's odd-even $(m,n)$-merging networks are
exactly optimal for $(m,n)=(3,4k+2)$ and $(4,4k+2)$ for $k \geq 0$
in terms of the number of comparators used.
For other cases where $m \leq 4$, the optimality of Batcher's
$(m,n)$-merging networks has been proved.
So we can conclude that Batcher's odd-even merge yields optimal
$(m,n)$-merging networks for every $m \leq 4$ and for every $n$.
The crucial part of the proof is characterizing the structure of
optimal $(2,n)$-merging networks.