|Abstract of Paper|
On Optimal Merging Networks
by Kazuyuki Amano and Akira Maruoka
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.