Optimal VLSI circuits for sorting

Abstract

This work describes a large number of constructions for sorting N integers in the range [0, M - 1], for N ≤ M ≤ N 2 , for the standard VLSI bit model. Among other results, we attain: VLSI sorter constructions that are within a constant factor of optimal size, for all M and almost all running times T . 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.