Fast parallel sorting algorithms
D. S. Hirschberg · Communications of the ACM · 1978
A parallel bucket-sort algorithm is presented that requires time O (log n ) and the use of n processors. The algorithm makes use of a technique that requires more space than the product of processors and time. A realistic model is used in which no memory contention is permitted. A procedure is also presented to sort n numbers in time O ( k log n ) using n 1 + 1 / k processors, for k an arbitrary integer. The model of computation for this procedure permits simultaneous fetches from the same memory location.
Cited by 97 works. doi:10.1145/359576.359582 Open-access PDF
Authors
References
- The Art of Computer Programming
- The Design and Analysis of Computer Algorithms
- Sorting networks and their applications
- Parallel Processing with the Perfect Shuffle
- Very high-speed computing systems
- The Parallel Evaluation of General Arithmetic Expressions
- Parallelism in Comparison Problems
- Cellular arrays for the solution of graph problems
- Optimal algorithms for parallel polynomial evaluation
- Bounds to Complexities of Networks for Sorting and for Switching