A Family of Parallel Sorting Algorithms
Yijie Han · 1985
We generalize Preparata''s sorting algorithm into a family of parallel sorting algorithms. This family of sorting algorithms sorts $n$ keys with $O(n~ log ^ \alpha n)$ processors in $O( \frac {1} { \alpha } log n)$ time units, where $\alpha$ is an arbitrary positive number less than 1. The computation model for this family of algorithms allows simultaneous fetches from the same memory cell.