Tech Report CS-91-20

Greed Sort: An Optimal External Sorting Algorithm for Multiple Disks

Mark H. Nodine and Jeffrey Scott Vitter

March 1991

Abstract:

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)