Improved parallel integer sorting without concurrent writing

Susanne Albers, Torben Hagerupt

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

23 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992
PublisherAssociation for Computing Machinery
Pages463-472
Number of pages10
ISBN (Electronic)089791466X
StatePublished - 1 Sep 1992
Externally publishedYes
Event3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992 - Orlando, United States
Duration: 27 Jan 199229 Jan 1992

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
VolumePart F129721

Conference

Conference3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992
Country/TerritoryUnited States
CityOrlando
Period27/01/9229/01/92

Fingerprint

Dive into the research topics of 'Improved parallel integer sorting without concurrent writing'. Together they form a unique fingerprint.

Cite this