Journal of the Association for Computing Machinery, Vol. 43, No. 1, January 1996, pp. 147–165.

The Asymptotic Complexity of Merging Networks

PETER BRO MILTERSEN

MIKE PATERSON

AND

JUN TARUI

Abstract. Let 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) ≤ \frac{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 → ∞:

M(m, n) ≥ \frac{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.

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

Copyright 1996 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.