Parallel Merge Sort
Richard J. Cole · SIAM Journal on Computing · 1988
We give a parallel implementation of merge sort on a CREW PRAM that uses n processors and $O(\log n)$ 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(\log n)$ time. The constant in the running time is still moderate, though not as small.
Cited by 724 works. doi:10.1137/0217049
Authors
References
- Parallelism in Comparison Problems
- Sorting inc logn parallel steps
- New Parallel-Sorting Schemes
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Routing, merging, and sorting on parallel models of computation
- Slowing down sorting networks to obtain faster sorting algorithms
- Searching, Merging, and Sorting in Parallel Computation
- Faster optimal parallel prefix sums and list ranking
- Optimal slope selection
- Tight Comparison Bounds on the Complexity of Parallel Sorting