An optimal parallel algorithm for integer sorting
- 1 January 1985
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 496-504
- https://doi.org/10.1109/sfcs.1985.9
Abstract
We assume a parallel RAM model which allows both concurrent writes and concurrent reads of global memory. Our algorithms are randomized: each processor is allowed an independent random number generator. However our stated resource bounds hold for worst case input with overwhelming likelihood as the input size grows. We give a new parallel algorithm for integer sorting where the integer keys are restricted to at most polynomial magnitude. Our algorithm costs only logarithmic time and is the first known where the product of the time and processor bounds are bounded by a linear function of the input size. These simultaneous resource bounds are asymptotically optimal. All previous known parallel sorting algorithms required at least a linear number of processors to achieve logarithmic time bounds, and hence were nonoptimal by at least a logarithmic factor.Keywords
This publication has 16 references indexed in Scilit:
- Efficient Parallel Pseudo-Random Number GenerationPublished by Springer Nature ,2000
- Parallel tree contraction and its applicationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Symmetric ComplementationJournal of the ACM, 1984
- On Synchronous Parallel Computations with Independent Probabilistic ChoiceSIAM Journal on Computing, 1984
- Tight bounds on the complexity of parallel sortingPublished by Association for Computing Machinery (ACM) ,1984
- A logarithmic time sort for linear size networksPublished by Association for Computing Machinery (ACM) ,1983
- Parallel computation and conflicts in memory accessInformation Processing Letters, 1982
- A fast probabilistic parallel sorting algorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- Parallel Prefix ComputationJournal of the ACM, 1980
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952