Optimal and sublogarithmic time randomized parallel sorting algorithms

This paper assumes a parallel RAM (random access machine) model which allows both concurrent reads and concurrent writes of a global memory. The main result is an optimal randomized parallel algorithm for INTEGER-SORT (i.e., for sorting n integers in the range [1, n]). This algorithm costs only logarithmic time and is the first known that is optimal: the product of its time and processor bounds is upper bounded by a linear function of the input size. Also given is a deterministic sublogarithmic time algorithm for prefix sum. In addition this paper presents a sublogarithmic time algorithm for obtaining a random permutation of n elements in parallel. And finally, sublogarithmic time algorithms for GENERAL-SORT and INTEGER-SORT are presented. Our sublogarithmic GENERAL-SORT algorithm is also optimal.

Duke Scholars

Author John H. Reif Computer Science