AbstractLet M(m, n) be the minimum number of comparators needed in a comparator network that merges m elements x_1 <= x_2 <= ... <= x_m and n elements y_1 <= y_2 <= ... <= y_n, where n >= m. Batcher's odd-even merge yields the following upper bound:
M(m, n) <= (1/2) (m + n) log_2 m + O(n);
in particular,
M(m, n) <= n log_2 n + O(n).
We prove the following lower bound that matches the upper bound above asymptotically as n >= m --> \infty:
M(m, n) >= (1/2) (m + n) log_2 m - O(n);
in particular,
M(m, n) >= n log_2 n - O(n).
Our proof technique extends to give similarly tight lower bounds for the size of monotone Boolean circuits for merging, and for the size of switching networks capable of realizing the set of permutations that arise from merging.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Preliminary versionA preliminary version of these results was presented in: Peter Bro Miltersen, Mike Paterson, and Jun Tarui. The asymptotic complexity of merging networks. In 33rd Annual Symposium on Foundations of Computer Science, pages 236-246, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- sorting and searching
General Terms: Algorithms, Theory
Additional Key Words and Phrases: Comparator network, merging, sorting
Selected papers that cite this one
- T. Leighton, Y. Ma, and T. Suel. On probabilistic networks for selection, merging, and sorting. Theory of Computing Systems, 30(6):559-582, November/December 1997.
Selected references
- Nicholas Pippenger and Leslie G. Valiant. Shifting graphs and their applications. Journal of the ACM, 23(3):423-432, July 1976.
- Andrew Chi-Chih Yao and Foong Frances Yao. Lower bounds on merging networks. Journal of the ACM, 23(3):566-571, July 1976.