Chapter 1 SORTING AND SELECTION ON PARALLEL DISK MODELS

Abstract Data explosion is an increasingly prevalent problem in every field of science. Traditional out-of-core models that assume a single disk have been found inadequate to handle voluminous data. As a result, models that employ multiple disks have been proposed in the literature. For example, the Parallel Disk Systems (PDS) model assumes D disks and a single computer. It is also assumed that a block of data from each of the D disks can be fetched into the main memory in one parallel I/O operation. In this article, we survey sorting and selection algorithms that have been devised for out-of-core models assuming multiple disks. We also consider practical implementations of parallel disk models. 1