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.