New Parallel-Sorting Schemes

Abstract

In this paper, we describe a family of parallel-sorting algorithms for a multiprocessor system. These algorithms are enumeration sortings and comprise the following phases: 1) count acquisition: the keys are subdivided into subsets and for each key we determine the number of smaller keys (count) in every subset; 2) rank determination: the rank of a key is the sum of the previously obtained counts; 3) data rearrangement: each key is placed in the position specified by its rank. The basic novelty of the algorithms is the use of parallel merging to implement count acquisition. By using Valiant's merging scheme, we show that n keys can be sorted in parallel with n log2n processors in time C log2n + o(log2n); in addition, if memory fetch conflicts are not allowed, using a modified version of Batcher's merging algorithm to implement phase 1), we show that n keys can be sorted with n^{1 +α}processors in time (C'/α a) log2n + o(log2n), thereby matching the performance of Hirschberg's algoithm, which, however, is not free of fetch conflicts.