Abstract
Algorithms for external sorting (i.e., sorting utilizing external memory) are wellknown for a few decades now. These methods were designed for systems with small amount of internal memory and magnetic tapes used as the external memory.
The magnetic tapes are characterized with purely sequential access, which strongly affected methods of external sorting. The magnetic tapes were replaced by magnetic hard drives, which brought the possibility of random access to the data.
However, the sequential access still remained faster, thus preferred. Most of the assumptions about hardware performance have changed in the last decade, especially with the emergence of SSD drives and with the development of nonvolatile memories.
In this paper, we propose a novel approach to external sort that reflects properties of modern hardware. We also provide an empirical comparison with existing methods, which are widely used in current database systems.