Towards optimal parallel bucket sorting (Q1098305): Difference between revisions

We present a simple deterministic parallel algorithm that runs on a concurrent-read concurrent-write 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.