Tech Report CS-90-04
Greed Sort: An Optimal External Sorting Algorithm for Multiple Disks
Mark H. Nodine and Jeffrey Scott Vitter
February 1990 - Replaced by CS-91-20
We present an optimal deterministic algorithm for external sorting on multiple disks. Our measure of performance is the number of input/output (I/O) operations. In each I/O, each disk can simultaneously transfer a block of data. Our algorithm improves upon the randomized optimal algorithm in [ViS] and the (non-optimal) commonly used technique of disk striping. The code is simple enough for easy implementation.
(complete text in pdf)