Aarhus University Seal / Aarhus Universitets segl

The asymptotic complexity of merging networks

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
Let M(m,n) be the minimum number of comparators needed in a comparator network that merges m elements x1⩽x2⩽. . .⩽xm and n elements y1 ⩽y2. . .⩽yn, where n⩾m. Batcher's odd-even merge yields the following upper bound: M(m,n)⩽1/2 (m+n)log2(m+1)+O( n); in particular, M(n,n)⩽n log2n+O(n). The authors prove the following lower bound that matches the upper bound above asymptotically as n⩾m→∞:M(m,n )⩾1/2(m+n)log2 (m+1)-O(m); in particular, M( n,n)⩾nlog2n-O (n). The authors' 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
Original languageEnglish
Title of host publication33rd Annual Symposium on Foundations of Computer Science, 1992. Proceedings.
Number of pages10
PublisherIEEE Computer Society Press
Publication year1992
ISBN (print)0-8186-2900-2
Publication statusPublished - 1992
EventAnnual Symposium on Foundations of Computer Science - Pittsburgh, PA, United States
Duration: 24 Oct 199227 Oct 1992
Conference number: 33


ConferenceAnnual Symposium on Foundations of Computer Science
LandUnited States
ByPittsburgh, PA

See relations at Aarhus University Citationformats

ID: 21706103