Improved Parallel Integer Sorting without Concurrent Writing

We show thatnintegers in the range 1, …, ncan be sorted stably on an EREW PRAM usingO(t) time andO(n( lognloglogn +(log n)2/t)) operations, for arbitrary givent⩾log n loglog n, and on a CREW PRAM usingO(t) time andO(n( logn +log n/2 t/log n )) operations, for arbitrary givent⩾log n. In addition, we are able to sortnarbitrary integers on a randomized CREW PRAM within the same resource bounds with high probability. In each case our algorithm is a factor of almostΘ: ( logn ) 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 previous sequential algorithm. We also show thatnintegers in the range 1, …, mcan be sorted inO((log n)2) time withO(n) operations on an EREW PRAM using a nonstandard word length ofO(log n loglog 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 of Fredman and Willard.

Authors

• Susanne Albers
• Torben Hagerup

Keywords

No keywords are indexed for this paper.