Lower bounds for merging networks (Q1854444)

A lower bound theorem is established for the number of comparators in a merging network. Let \(M(m,n)\) be the least number of comparators required in the \((m,n)\)-merging networks, and let \(C(m,n)\) be the number of comparators in Batcher's \((m,n)\)-merging network, respectively. We prove for \(n\geq 1\) that \(M(4,n)=C(4,n)\) for \(n\equiv 0,1,3\bmod 4, M(4,n)\geq C(4,n)-1\) for \(n\equiv 2\bmod 4\), and \(M(5,n)=C(5,n)\) for \(n\equiv 0,1,5\bmod 8\). Furthermore Batcher's \((6,8k+6)\)-, \((7,8k+7)\)-, and \((8,8k+8)\)-merging networks are optimal for \(k\geq 0\). Our lower bound for \((m,n)\)-merging networks, \(m\leq n\), has the same terms as \(C(m,n)\) has as far as \(n\) is concerned. Thus Batcher's \((m,n)\)-merging network is optimal up to a constant number of comparators, where the constant depends only on \(m\). An open problem posed by \textit{A. C.-C. Yao} and \textit{F. F. Yao} [J. Assoc. Comput. Mach. 23, 566-571 (1976; Zbl 0335.68034)] is solved: \(\lim_{n\to\infty}M(m,n)/n=\lceil\log m\rceil/2+m/2^{\lceil\log m\rceil}\).