zbMATH — the first resource for mathematics

Optimal VLSI circuits for sorting. (English) Zbl 0665.68051
Several effective algorithms for sorting N integers in the range [0,M-1], for \(N\leq M\leq N^ 2\), are presented. The standard VLSI bit model and its restricted version with input/output ports located along the boundary of the circuits are considered as computing models [C. D. Thompson, A complexity theory for VLSI. Ph. D. dissertation. Computer Science Department, Carnegie-Mellon Univ., Pitsburgh, Pa., 1980]. This paper together with the earlier works [G. Bilardi and F. P. Preparata, IEEE Trans. Comput. C-33, 646-651 (1984; Zbl 0537.68062); T. H. Leighton, ibid. C-34, 344-354 (1985; Zbl 0556.68024)] provide a large variety of optimal construction for VLSI sorters, thereby establishing the tightness of several area-time tradeoffs. The most original contribution of the paper is so called aligned merging network representing a fundamentally new sorting construction.
Reviewer: J.Hromkovič

68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI