Towards optimal parallel bucket sorting (Q1098305)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Towards optimal parallel bucket sorting |
scientific article |
Statements
Towards optimal parallel bucket sorting (English)
0 references
1987
0 references
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.
0 references
deterministic parallel algorithm
0 references
restricted sorting problem
0 references
