Affordable Access

Publisher Website

Accelerating certain outputs of merging and sorting networks

Theoretical Computer Science
Publication Date
DOI: 10.1016/j.tcs.2009.04.024
  • Merging
  • Sorting
  • Comparator Networks
  • Zero–One Principle
  • Acceleration


Abstract This work studies comparator networks in which several of the outputs are accelerated. That is, they are generated much faster than the other outputs, and this without hindering the other outputs. We study this acceleration in the context of merging networks and sorting networks. The paper presents a new merging technique, the Tri-section technique, that separates, using a depth 1 network, two sorted sequences into three sets, such that every key in one set is smaller than or equal to any key in the following set. After this separation, each of these sets can be sorted separately, causing the above acceleration of certain outputs. An additional contribution of this paper concerns the well-known 0 – 1 Principle [D.E. Knuth, The Art of Computer Programming vol. 3: Sorting and Searching, second edition, Addison-Wesley, 1998]. This principle is a powerful tool that simplifies the construction and analysis of comparator networks. The paper demonstrates that, in some cases, there is a better tool for achieving the same goal. In the case at hand, this new tool simplifies one of our proofs by having fewer special cases than the classical 0 – 1 Principle. A second additional contribution concerns Batcher’s merging techniques. It was shown in [T. Levy, A. Litman, On Merging Networks, Technical Report CS-2007-16, Technion, Department of Computer Science, 2007] that all published merging networks, whose width is a power of 2, are a natural generalization of Batcher’s odd–even merging network. All these published merging networks are of minimal depth and have no degenerate comparators. This raises the following question. Is there a merging network, having the above properties, that is not a natural generalization of Batcher’s odd–even merging network? The Tri-section technique provides a positive answer to this question.

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times

More articles like this

Bounds on the size of merging networks

on Discrete Applied Mathematics Jan 01, 1995

Lower Bounds for Merging Networks

on Information and Computation Jan 01, 2001

Some minimum merging networks

on Theoretical Computer Science Jan 01, 2004

Parallel algorithms for merging and sorting

on Information Sciences Jan 01, 1991
More articles like this..