Tech Report CS-92-08
Optimal Deterministic Sorting on Parallel Disks
Mark H. Nodine and Jeffrey Scott Vitter
We present an optimal deterministic algorithm called Balance Sort 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 of Vitter and Shriver as well as the (non-optimal) commonly-used technique of disk striping. It also improves upon our earlier merge-based sorting algorithm in that it has smaller constants hidden in the big~oh notation, it is possible to implement using only striped writes (but independent reads), and it has application to parallel memory hierarchies.