An Efficient External-Memory Sorting Algorithm

Abstract

External-memory sorting is a well-versed subject, with a history going back several decades. However, current implementations of external-memory sorting algorithms are not able to fully take advantage of the power of modern hardware. The reason for this is twofold: (1) they use a computationally-expensive mergesort approach, which can create a bottleneck during processing; (2) their management of I/O resources prevents them from achieving maximum I/O bandwidth. In this paper, we outline the construction of an external-memory distribution sort algorithm that utilizes available resources much more effectively.