Technical Report CS-2008-10

TR#:CS-2008-10
Class:CS
Title: Accelerating certain outputs of merging and sorting networks
Authors: Tamir Levi and Ami Litman
PDFCS-2008-10.pdf
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 \emph{Tri-section technique}, that separates, by a depth one network, two sorted sequences into three sets, such that every key in one set is smaller 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 of KNUTH. 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 to achieve the same goal. In the case at hand, this new tool simplifies one of our proves by having fewer special cases than the classical 0-1 Principle.

A second additional contribution concerns Batcher's merging techniques. It was shown that all published merging networks, whose width is a power of two, are a natural generalization of Batcher's odd-even merging network. All these published networks are of minimal depth and have no degenerate comparators. This raises the following question. Is there a network, having the above properties, that is not a natural generalization of Batcher's odd-even network? The Tri-section technique provides a positive answer to this question.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2008/CS/CS-2008-10), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2008
To the main CS technical reports page

Computer science department, Technion
admin