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)
| Page Owner: John Bazik | Last Modified: Fri Feb 9 17:44:32 2007 |