Parallel sorting by over partitioning
Hui Li, Kenneth C. Sevcik · 1994
A new approach to parallel sorting called Parallel Sorting by OverPartitioning (PSOP) is presented.The approach limits the communication cost by moving each element between processors at most once, and leads to good load balancing with high probability y.The PSOP framework can be applied to both comparison and non-comparison sorts.Implementations on the KSR1 and Hector shared memory multiprocessors show that PSOP achieves nearly linear speedup and outperforms alternative approaches.An analytical model for PSOP has been developed that predicts the performance within 10% accuracy.