Tech Report CS-91-20

Greed Sort: An Optimal External Sorting Algorithm for Multiple Disks

Mark H. Nodine and Jeffrey Scott Vitter

March 1991


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 a recent randomized optimal algorithm and the (non-optimal) commonly used technique of disk striping. The code is simple enough for easy implementation.

(complete text in pdf)