A new approach to parallel sorting called Parallel Sorting by Over Partitioning (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. The PSOP framework can be applied to both comparison and non-comparison sorts. Implemen- tations on the KSR1 and Hector shared memory multipro- cessors 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. Key Words: Parallel Sorting, Load Balance, Overparti- tioning, Oversampling, COMA and NUMA Multiprocessors.