THE ASYMPTOTIC COMPLEXITY OF MERGING NETWORKS

Let M(m, n) be the minimum number of comparators needed in a comparato r network that merges m elements x(1) less than or equal to x(2) less than or equal to ... less than or equal to x(m) and n elements y(1) le ss than or equal to y(2) less than or equal to ... less than or equal to y(n), where n greater than or equal to m. Batcher's odd-even merge yields the following upper bound: M(m,n) less than or equal to 1/2(m n)log(2)m + O(n); in particular, M(n,n) less than or equal to n log(2 )n + O(n). We prove the following lower bound that matches the upper b ound above asymptotically as n greater than or equal to m --> infinity : M(m,n) greater than or equal to 1/2(m + n)log(2)m - O(m); in particu lar, M(n,n) greater than or equal to 1/2 n log(2)n - O(n). Our proof t echnique extends to give similarly tight Lower bounds for the size of monotone Boolean circuits for merging, and for the size of switching n etworks capable of realizing the set of permutations that arise from m erging.