Optimal and sublogarithmic time randomized parallel sorting algorithms

Abstract.We assume a parallel RAM model which allows both concurrent reads and concurrent writes of a global memory. Our main result is an optimal randomized parallel algorithm for INTE-GER SORT (i.e., for sorting n integers in the range [1;n]). Our algorithm costs only logarithmic time and is the rst known that is optimal: the product of its time and processor bounds is upper bounded by a linear function of the input size. We also give a deterministic sub-logarithmic time algorithm for pre x sum. In addition we present a sub-logarithmic time algorithm for obtaining a random permutation of n elements in parallel. And nally, we present sub-logarithmic time algorithms for GENERAL SORT and INTEGER SORT. Our sublogarithmic GENERAL SORT algorithm is also optimal