Quick- instead of Merge-sort for pipelines systems

Abstract

This paper proposes an external sorting algorithm for large data as an alternative to the widely used merge-sort algorithm. The algorithm we present is an application of the widely known quick-sort algorithm to large sequences of data stored externally on a disk device. The problem with the merge-sort algorithm is not its time complexity but the large amount of time it requires to output its first results. This is a serious problem in the context of pipelined processing, since the operations consuming its result will have to wait all that time before they can start their processing, thus limiting the degree of vertical parallelism achievable by pipelined processing Using quick-sort instead of merge-sort for external sorting in pipelined data processing systems results in an optimization in the order of $log N$ (where N is the size of the data sequence to be sorted) for the entire query pipeline where the sorting operation is involved.