Parallel merge sort
- 1 October 1986
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 511-516
- https://doi.org/10.1109/sfcs.1986.41
Abstract
We give a parallel implementation of merge sort on a CREW PRAM that uses n processors and O(logn) time; the constant in the running time is small. We also give a more complex version of the algorithm for the EREW PRAM; it also uses n processors and O(logn) time. The constant in the running time is still moderate, though not as small.Keywords
This publication has 8 references indexed in Scilit:
- Tight bounds on the complexity of parallel sortingPublished by Association for Computing Machinery (ACM) ,1984
- Improved upper bounds on shellsortPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Applying Parallel Computation Algorithms in the Design of Serial AlgorithmsJournal of the ACM, 1983
- Searching, Merging, and Sorting in Parallel ComputationIEEE Transactions on Computers, 1983
- Sorting inc logn parallel stepsCombinatorica, 1983
- Routing, merging and sorting on parallel models of computationPublished by Association for Computing Machinery (ACM) ,1982
- New Parallel-Sorting SchemesIEEE Transactions on Computers, 1978
- Parallelism in Comparison ProblemsSIAM Journal on Computing, 1975