Optimal and sublogarithmic time randomized parallel sorting algorithms


Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Rajasekaran, S; Reif, JH

Published Date

  • January 1, 1989

Published In

Volume / Issue

  • 18 / 3

Start / End Page

  • 594 - 607

International Standard Serial Number (ISSN)

  • 0097-5397

Digital Object Identifier (DOI)

  • 10.1137/0218041

Citation Source

  • Scopus