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

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 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)