# The Library

### The asymptotic complexity of merging networks

Tools

UNSPECIFIED.
(1996)
*The asymptotic complexity of merging networks.*
JOURNAL OF THE ACM, 43
(1).
pp. 147-165.
ISSN 0004-5411

**Full text not available from this repository.**

## Abstract

Let M(m, n) be the minimum number of comparators needed in a comparator 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) less 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 bound 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 particular, M(n,n) greater than or equal to 1/2 n log(2)n - O(n). Our 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.

Item Type: | Journal Article |
---|---|

Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |

Journal or Publication Title: | JOURNAL OF THE ACM |

Publisher: | ASSOC COMPUTING MACHINERY |

ISSN: | 0004-5411 |

Date: | January 1996 |

Volume: | 43 |

Number: | 1 |

Number of Pages: | 19 |

Page Range: | pp. 147-165 |

Publication Status: | Published |

URI: | http://wrap.warwick.ac.uk/id/eprint/18594 |

Data sourced from Thomson Reuters' Web of Knowledge

### Actions (login required)

View Item |