×

A sequential sorting network analogous to the Batcher merge. (English) Zbl 0734.68030

Summary: We present a network of delay \(\log_ 2N\), whose comparators have only \(\log_ 2N\) different lengths with maximum length N/2. This network is log-sequential in that it will sort N data items when they are passed through it \(\log_ 2N\) times. The design, which is related to the Batcher odd-even merge, is distinctly different from the first known example of a log-delay log-sequential network, due to M. Dowd, Y. Perl, L. Rudolf, and M. Saks [The sequential balanced sorting network, Institute of Technology Research, No.10, New Jersey]. It is quite probably the “best possible” sorting network.

MSC:

68P10 Searching and sorting
68M10 Network design and communication in computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ajtai M., Proc. 15th Annual ACM Symposium on the Theory of Computing (SIGACT) (1983)
[2] Batcher K. E., Proc. 1968 Spring Joint Comp. Conf. pp 307– (1968)
[3] Dowd M., The sequential balanced sorting network · Zbl 0698.68042
[4] Gibbons A. M., Efficient Parallel Algorithms (1988) · Zbl 0771.68015
[5] Gordon D, Algorithmica (1988)
[6] Knuth D. E., Sorting and searching, volume III of the Art of Computer Programming (1973) · Zbl 0302.68010
[7] DOI: 10.1137/0207022 · Zbl 0379.68024 · doi:10.1137/0207022
[8] Williamson S. G., Combinatorics for Compuici Science (1983)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.