Minimum storage sorting networks

This paper analyzes how to sort n k-bit numbers in a minimum storage network. The techniques also give new AT2 lower bounds for a VLSI sorting model. The principal results in this paper are as follows. * Lower bounds are given for the minimum storage (and area) needed to sort n k-bit numbers, and accompanying upper bounds (sorting networks) are presented, which match the lower bounds, up to a constant factor. * Sharp bounds are derived, which demonstrate that theminimum storage requirements depend quite strongly on the I/O schedule, and on the sorting model. * AT2 lower bounds are established for a VLSI device that sorts n k-bit numbers where k ≫ log n.