Efficiently managing parallel resources is the natural and, with the disappearance of Moore’s Law, possibly the only way to increase the computational power of computing systems. Since disk access is slow, this predicament has been understood for quite some time in the storage community, where large clusters of parallel independent disks are routinely used to handle ever-increasing data volumes. Adapting classical in-memory algorithms, such as sorting, to such architectures while avoiding disk access bottlenecks is difficult; this paper introduces a new out-of-core randomized sorting algorithm: randomized cyclic distribution (RCD) sort.

In RCD, the data is partitioned into several buckets, using judiciously chosen pivot values. These buckets are stored into the memory blocks of parallel disks, and the overall process is recursively applied until the dataset is small enough to be handled in memory. The mapping of buckets to blocks lies at the core of the algorithm and its efficiency; here, randomization is used to pick a cycle order of the disk numbers, and blocks are allocated in a round-robin manner accordingly. The paper studies the theoretical probabilistic properties of RCD and its variants, showing its expected input/output optimality, and its practical performance, providing experimental data supporting these claims, particularly when dealing with small numbers of disks. This disk allocation approach is a vast improvement over a straightforward static disk striping solution. This somewhat mathematical paper should be of interest to scientists and engineers interested in optimizing algorithms based on external memory.