The asymptotic complexity of merging networks
The asymptotic complexity of merging networks
Let M(m,n) be the minimum number of comparators needed in a comparator network that merges m elements x/sub 1/<or=x/sub 2/<or=. . .<or=x/sub m/ and n elements y/sub 1/<or=y/sub 2/. . .<or=y/sub n/, where n>or=m. Batcher's odd-even merge yields the following upper bound: M(m,n)<or=/sup 1///sub 2/(m+n)log/sub 2/(m+1)+O(n); in particular, M(n,n)<or=nlog/sub 2/n+O(n). …