PSRS
Parallel Sorting by Regular Sampling (PSRS) PSRS is a structured parallel sorting algorithm designed for shared memory or distributed systems. It combines local sorting, deterministic sampling, and balanced redistribution. Unlike naive sample sort, PSRS uses regular sampling to guarantee better load balance without heavy randomness. Problem Given $n$ elements distributed across $p$ processors, sort them in nondecreasing order. Each processor initially holds about $n/p$ elements. Algorithm PSRS proceeds in five...