Minimum Storage Sorting Networks

Abstract

This paper analyzes how to sort n k-bit numbers in a minimum storage network. The techniques also give new AT <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> 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 the minimum storage requirements depend quite strongly on the I/O schedule, and on the sorting model. • AT <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> lower bounds are established for a VLSI device that sorts n k-bit numbers where k < log n.