Improved parallel integer sorting without concurrent writing

摘要

We show that n integers in the range 1..n can be stably sorted on an EREW PRAM using O((log n)1/2) time, O(n(log n)1/2(log log n)1/2) operations and O(n) space. In addition, we are able to stably sort n integers in the range 1..n on a deterministic CREW PRAM in O((log n)3/2) time with O(n(log n)1/2) operations and O(n) space and to stably sort n arbitrary integers on a randomized CREW PRAM within the same complexity bounds with high probability. In each case our algorithm is closer to optimality than all previous algorithms for the stated problem in the stated model, and our third result matches the operation count of the best known sequential algorithm. We also show that m integers in the range 1..m can be sorted in O((log n)2) time with O(n) operations on an EREW PRAM using a nonstandard word length of O(log n log log n log m) bits, thereby greatly improving the upper bound on the word length necessary to sort integers with a linear time-processor product, even sequentially. Our algorithms were inspired by, and in one case directly use, the fusion trees recently introduced by Fredman and Willard.