1988/08/01 by Richard Cole · 9 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Constant (computer programming) #Database #Log-log plot #Mathematics #Merge (version control) #Merge algorithm #Merge sort #Parallel algorithm #Parallel computing #Programming language #Running time #Sorting algorithm #sort
paper · doi:10.1137/0217049
openalex publication_date 1988/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
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.