Parallel Merge Sort

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.

Authors

• Richard Cole 0001

Keywords

• Sorting
• Phase change random access memory
• Circuits
• Radio access networks
• Graph theory
• Read-write memory
• Merging
• Parallel algorithms
• Algorithm design and analysis
• Computational modeling
• Merge Sort
• Running Time
• Start Of Stage
• External Nodes
• Merging Procedure