Better understanding of batcher's merging networks

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

We reinvestigate the known bitonic and odd-even merging networks of Batcher. For each of the two networks we do the following:. We characterize the input vectors which are sorted by the networks. Those vectors are recursively balanced for the appropriate definition of balance. The set of those vectors is much larger than the set of vectors previously known to be sorted by the network. We also characterize the output vectors obtainable by applying the network to arbitrary input vectors. Those vectors satisfy the appropriate definition of recursive dominance. This characterization is used to show that this merging network cannot be a block in a periodic sorting network composed of a sequence of identical blocks. The general purpose of this investigation is to achieve more insight into the structure of those classic merging networks. Such insight can help in the design and analysis of new merging and sorting networks which hopefully will have some extra advantages.

Original languageEnglish (US)
Pages (from-to)257-271
Number of pages15
JournalDiscrete Applied Mathematics
Volume25
Issue number3
DOIs
StatePublished - Nov 1989

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Better understanding of batcher's merging networks'. Together they form a unique fingerprint.

Cite this