TY - GEN

T1 - Improved parallel integer sorting without concurrent writing

AU - Albers, Susanne

AU - Hagerupt, Torben

N1 - Funding Information:
W-6600 Saarbriicken, Germany. Research supported by a graduate fellowship of the Deutsche Forschungsgemeinscha ft. *Max-Planck-lns titut fiir Informatikj W-6600 Saarbriicken, Germany. Supported in part by the Jeutsche Forschungsge-meinschaft, SFB 124, TP B2, VLSI Entwurfsmethoden und Par-allelitit, and in part by the ESPRIT II Basic Research Actions Program of the EC under contract No. 3075 (project ALCOM).

PY - 1992/9/1

Y1 - 1992/9/1

N2 - We show that n integers in the range 1. n can be stably sorted on an EREW PRAM using O(log n)3/2(log 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 n 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(lognloglognlogm) 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.

AB - We show that n integers in the range 1. n can be stably sorted on an EREW PRAM using O(log n)3/2(log 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 n 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(lognloglognlogm) 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.

UR - http://www.scopus.com/inward/record.url?scp=84969164263&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84969164263

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 463

EP - 472

BT - Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992

PB - Association for Computing Machinery

T2 - 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992

Y2 - 27 January 1992 through 29 January 1992

ER -