Optimal VLSI circuits for sorting
Richard Cole, Alan R. Siegel · Journal of the ACM · 1988
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.