An Efficient Parallel VLSI Sorting Architecture

We present a new parallel sorting algorithm that uses a fixed-size sorter iteratively tosort inputs of arbitrary size. A parallel sorting architecture based on this algorithm isproposed. This architecture consists of three components, linear arrays that supportconstant-time operations, a multilevel sorting network, and a termination detection tree,all operating concurrently in systolic processing fashion. The structure of this sortingarchitecture is simple and regular, highly suitable for VLSI realization. Theoreticalanalysis and experimental data indicate that the performance of this architecture islikely to be excellent in practice