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 language | English (US) |
---|---|
Pages (from-to) | 257-271 |
Number of pages | 15 |
Journal | Discrete Applied Mathematics |
Volume | 25 |
Issue number | 3 |
DOIs | |
State | Published - Nov 1989 |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Applied Mathematics