# 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č

##### MSC:
 68P10 Searching and sorting 68Q25 Analysis of algorithms and problem complexity
##### Keywords:
parallel sorting; VLSI algorithms; area-time tradeoffs
Full Text: