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