Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms
- 1 June 1989
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 18 (3) , 594-607
- https://doi.org/10.1137/0218041
Abstract
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 sub-logarithmic GENERAL_SORT algorithm is also optimal.Keywords
This publication has 12 references indexed in Scilit:
- Efficient Parallel Pseudo-Random Number GenerationPublished by Springer Nature ,2000
- A logarithmic time sort for linear size networksJournal of the ACM, 1987
- Symmetric ComplementationJournal of the ACM, 1984
- On Synchronous Parallel Computations with Independent Probabilistic ChoiceSIAM Journal on Computing, 1984
- Parallel computation and conflicts in memory accessInformation Processing Letters, 1982
- Parallel Prefix ComputationJournal of the ACM, 1980
- Fast probabilistic algorithms for hamiltonian circuits and matchingsJournal of Computer and System Sciences, 1979
- Algorithm 447: efficient algorithms for graph manipulationCommunications of the ACM, 1973
- On the Distribution of the Number of Successes in Independent TrialsThe Annals of Mathematical Statistics, 1956
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952