An Optimal Parallel Algorithm for Integer Sorting

We assume a parallel RAM model which allows both concurrent writes and concurrent reads of global memory. Our algorithms are randomized: each processor is allowed an independent random number generator. However our stated resource bounds hold for worst case input with overwhelming likelihood as the input size grows. We give a new parallel algorithm for integer sorting where the integer keys are restricted to at most polynomial magnitude. Our algorithm costs only logarithmic time and is the first known where the product of the time and processor bounds are bounded by a linear function of the input size. These simultaneous resource bounds are asymptotically optimal. All previous known parallel sorting algorithms required at least a linear number of processors to achieve logarithmic time bounds, and hence were nonoptimal by at least a logarithmic factor.

Authors

• John H. Reif

Keywords

• Parallel algorithms
• Sorting
• Read-write memory
• Random access memory
• Random number generation
• Polynomials
• Concurrent computing
• Registers
• Cost function
• Arithmetic
• Parallel Algorithm
• Integer Sorting
• Input Size
• Parallel Model
• Sequential Algorithm
• Log Time
• Depth-first
• Sorting Algorithm
• Number Of Processors
• N Log N
• Lower Bound
• Upper Bound
• Optimization Algorithm
• Parallelization
• Memory Cells
• Constant Factor
• Random Permutations
• Hypergeometric Distribution
• Key Values