A Note on Coarse Grained Parallel Integer Sorting
A. Chan, Fabian Gregor Dehne · Kluwer Academic Publishers eBooks · 2005
We observe that for n/p ≥ p, which is usually the case in practice, there exists a very simple, deterministic, optimal coarse grained parallel integer sorting algorithm with 24 communication rounds (6 n/p-relations and 18 (p-relations), O(n/p) memory per processor and O(n/p) local computation. Experimental data indicates that the algorithm has very good performance in practice.