Waste makes haste: tight bounds for loose parallel sorting
Torben Hagerup, Rajeev Raman · 1992
Conventional parallel sorting requires the n input keys to be output in an array of size n, and is known to take Omega (log n/log log n) time using any polynomial number of processors. The lower bound does not apply to the more 'wasteful' convention of padded sorting, which requires the keys to be output in sorted order in an array of size (1+o(1))n. The authors give very fast randomised CRCW PRAM algorithms for several padded-sorting problems. Applying only pairwise comparisons to the input and using kn processors, where 2>