The asymptotic complexity of merging networks

Publisher Website
Google Scholar
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 m , where n ≥ m. Batcher's odd-even merge yields the following upper bound: M(m,n) ≤ ½(m + n)log 2 m + O(n); in particular, M(n,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) ≥ ½(m+n)log 2 m - O(m) in particular, M(n,n) ≥ n log 2 - O(n). Our proof technique extends to give similarily 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.

This publication has 3 references indexed in Scilit: