Towards optimal parallel bucket sorting (Q1098305): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Sorting in \(c \log n\) parallel steps / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Deterministic coin tossing with applications to optimal parallel list ranking / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A universal interconnection pattern for parallel computers / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Fast parallel sorting algorithms / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Axioms and hulls / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Parallel computation and conflicts in memory access / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Design and implementation of an efficient priority queue / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Implementation of simultaneous memory address access in models that forbid it / rank | |||
Normal rank | |||
Latest revision as of 15:53, 18 June 2024
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
