Optimal VLSI circuits for sorting
- 1 October 1988
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 35 (4) , 777-809
- https://doi.org/10.1145/48014.48017
Abstract
This work describes a large number of constructions for sortingNintegers in the range [0,M- 1], forN≤M≤N2, for the standard VLSI bit model. Among other results, we attain: VLSI sorter constructions that are within a constant factor of optimal size, for allMand almost all running timesT. a fundamentally new merging network for sorting numbers in a bit model. new organizational approaches for optimal tuning of merging networks and the proper management of data flow.Keywords
This publication has 10 references indexed in Scilit:
- The influence of key length on the area-time complexity of sortingPublished by Springer Nature ,2005
- Area-time lower-bound techniques with applications to sortingAlgorithmica, 1986
- Tight chip area lower bounds for discrete Fourier and Walsh-Hadamard transformationsInformation Processing Letters, 1985
- Tight Bounds on the Complexity of Parallel SortingIEEE Transactions on Computers, 1985
- Minimum Storage Sorting NetworksIEEE Transactions on Computers, 1985
- A Minimum Area VLSI Network for O(log n) Time SortingIEEE Transactions on Computers, 1985
- The VLSI optimality of the aks sorting networkInformation Processing Letters, 1985
- An Architecture for Bitonic Sorting with Optimal VLSI PerformnanceIEEE Transactions on Computers, 1984
- The complexity of sorting on distributed systemsInformation and Control, 1984
- The VLSI Complexity of SortingIEEE Transactions on Computers, 1983