The complexity of parallel sorting
- 1 January 1985
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 532-540
- https://doi.org/10.1109/sfcs.1985.58
Abstract
We consider PRAM's with arbitrary computational power for individual processors, infinitely large shared memory and "priority" writeconflict resolution. The main result is that sorting n integers with n processors requires Ω(√log n) steps in this strong model. We also show that computing any symmetric polynomial (e.g. the sum or product) of n integers requires exactly log2n steps, for any finite number of processors.Keywords
This publication has 6 references indexed in Scilit:
- One, two, three . . . infinity: lower bounds for parallel computationPublished by Association for Computing Machinery (ACM) ,1985
- Tight bounds on the complexity of parallel sortingPublished by Association for Computing Machinery (ACM) ,1984
- ∑11-Formulae on finite structuresAnnals of Pure and Applied Logic, 1983
- Sorting inc logn parallel stepsCombinatorica, 1983
- Parallelism in Comparison ProblemsSIAM Journal on Computing, 1975
- A Combinatorial TheoremJournal of the London Mathematical Society, 1950