Critical Evaluation of Existing External Sorting Methods in the Perspective of Modern Hardware
Martin Kruliš · DATESO · 2015
External sorting methods which are designed to order large amounts of data stored in persistent memory are well known for decades. These methods were originally designed for systems with small amount of operating (internal) memory and magnetic tapes used as external mem- ory. Data on magnetic tapes has to be accessed in strictly serial man- ner and this limitation shaped the external sorting algorithms. In time, magnetic tapes were replaced with hard drives which are now being re- placed with solid state drives. Furthermore, the amount of the operating memory in mainstream servers have increased by orders of magnitude and the future may hold even more impressive innovations such as non- volatile memories. As a result, most of the assumptions of the external sorting algorithms are not valid any more and these methods needs to be innovated to better reect the hardware of the day. In this work, we critically evaluate original assumptions in empirical manner and propose possible improvements.