Aarhus University Seal / Aarhus Universitets segl

The asymptotic complexity of merging networks

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Department of Computer Science
Let M(m,n) be the minimum number of comparatorsneeded in a comparator network that merges m elements x1≤x2≤&cdots;≤xm and n elements y1≤y2≤&cdots;≤yn , where n≥m . Batcher's odd-even merge yields the following upper bound: Mm,n≤1 2m+nlog 2m+on; in particular, Mn,n≤nlog 2n+On. We prove the following lower bound that matches the upper bound above asymptotically as n≥m→∞: Mm,n≥1 2m+nlog 2m-Om; in particular, Mn,n≥nlog 2n-On. 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.
Original languageEnglish
JournalAssociation for Computing Machinery. Journal
Volume43
Issue1
Pages (from-to)147-165
ISSN0004-5411
DOIs
Publication statusPublished - 1996

See relations at Aarhus University Citationformats

ID: 21706012