ComputingComputer EngineeringComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingData ParallelismParallel ArchitecturesParallel Computer ArchitectureParallel Performance AnalysisParallel SortingSorting AlgorithmsMergeMerge SortParallel MergingParallel Sort AlgorithmsParallel Sorting AlgorithmsPram Algorithms
Abstract. We give a parallel implementation of merge sort on a CREW PRAM that uses n processors and O(logn) time; the con-stant 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. 1.
7
Sorting inc logn parallel steps
Miklós Ajtai, János Komlós, Endre Szemerédi · COMBINATORICA · 1983 · 513 citations
Parallelism in Comparison Problems
Leslie G. Valiant · SIAM Journal on Computing · 1975 · 401 citations
Searching, Merging, and Sorting in Parallel Computation
Kruskal · IEEE Transactions on Computers · 1983 · 166 citations