Waste makes haste: tight bounds for loose parallel sorting

Conventional parallel sorting requires the n input keys to be output in an array of size n, and is known to take Ω(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 ⩽ k ⩽ n, they can padded-sort n keys in O(log n/log k) time with high probability (WHP), which is the best possible (expected) run time for any comparison-based algorithm. They also show how to padded-sort n independent random numbers in O(log_*n) time WHP with O(n) work, which matches a recent lower bound, and how to padded-sort n integers in the range 1..n in constant time whp using n processors. If the integer sorting is required to be stable, they can still solve the problem in O(log log n/log k) time WHP using kn processors, for any k with 2 ⩽ k ⩽ log n. The integer sorting results require the nonstandard OR PRAM. As an application of the padded-sorting algorithms, they can solve approximate prefix summation problems of size n with O(n) work in constant time WHP on the OR PRAM, and in O(log log n) time WHP on standard PRAM variants