Optimal Sorting Algorithms for Parallel Computers
Baudet, Stevenson · IEEE Transactions on Computers · 1978
The problem of sorting a sequence of n elements on a parallel computer with k processors is considered. The algorithms we present can all be run on a single instruction stream multiple data stream computer. For large n, each achieves an asymptotic speed-up ratio of k with respect to the best sequential algorithm, which is optimal in the number of processors used.
Cited by 154 works. doi:10.1109/tc.1978.1674957
Authors
References
- The Art of Computer Programming
- The Art of Computer Programming: Volume 3: Sorting and Searching
- Sorting and Searching
- Sorting networks and their applications
- Parallel Processing with the Perfect Shuffle
- The ILLIAC IV Computer
- Some Computer Organizations and Their Effectiveness
- The Illiac IV system
- Computer organization and algorithms for very-high speed computations.
- B72-3 Computer Structures, Readings and Examples