Towards optimal parallel bucket sorting (Q1098305)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Towards optimal parallel bucket sorting |
scientific article; zbMATH DE number 4037231
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Towards optimal parallel bucket sorting |
scientific article; zbMATH DE number 4037231 |
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
0 references
0.92070645
0 references
0.9127227
0 references
0 references
0.90482295
0 references
