GREED SORT - OPTIMAL DETERMINISTIC SORTING ON PARALLEL DISKS

We present an algorithm for sorting efficiently with parallel two-leve l memories. Our main result is an elegant, easy-to-implement, optimal, deterministic algorithm for external sorting with D disk drives. This result answers in the affirmative the open problem posed by Vitter an d Shriver of whether an optimal algorithm exists that is deterministic . Our measure of performance is the number of parallel input/output (I /O) operations, in which each of the D disks can simultaneously transf er a block of B contiguous records. We assume that internal memory can hold M records. Our algorithm sorts N records in the optimal bound of Theta((N/BD)log(N/B)/log(M/B)) deterministically, and thus it improve s upon Vitter and Shriver's optimal randomized algorithm as well as th e well-known deterministic but nonoptimal technique of disk striping. It is also practical to implement.