On parallel integer sorting

Abstract

We present an optimal algorithm for sorting n integers in the range [1, n^c ] (for any constant c) for the EREW PRAM model where the word length is n^ε, for any ε>0. Using this algorithm, the best known upper bound for integer sorting on the (O(logn) word length) EREW PRAM model is improved. In addition, a novel parallel range reduction algorithm which results in a near optimal randomized integer sorting algorthm is presented. For the case when the keys are uniformly distributed integers in an arbitrary range, we give an algorithm whose expected running time is optimal.