Accelerating certain outputs of merging and sorting networks

AbstractThis 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