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 -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.
['Albert Chan', 'Frank K. H. A. Dehne']
A NOTE ON COARSE GRAINED PARALLEL INTEGER SORTING