Towards optimal parallel bucket sorting

We present a simple deterministic parallel algorithm that runs on a CRCW PRAM and sorts n integers of size polynomial in n in time O(log n) using O( n log log n log n ) processors. It is closer to optimality than any previously known deterministic algorithm that solves the stated restricted sorting problem in polylog time.

Authors

• Torben Hagerup

Keywords

No keywords are indexed for this paper.