Towards optimal parallel bucket sorting

DOI10.1016/0890-5401(87)90062-9zbMath0636.68078OpenAlexW2057697239WikidataQ61051153 ScholiaQ61051153MaRDI QIDQ1098305

Torben Hagerup

Publication date: 1987

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(87)90062-9

zbMATH Keywords

deterministic parallel algorithmrestricted sorting problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items

Planarity testing in parallel, Parallel integer sorting using small operations, Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM, A parallel bucket sort, ERCW PRAMs and optical communication, Conservative algorithms for parallel and sequential integer sorting, Improved deterministic parallel integer sorting, Breadth-first traversal of trees and integer sorting in parallel, Optimal parallel algorithms for path problems on planar graphs, Approximating Huffman codes in parallel, Parallel iterated bucket sort, Improved fast integer sorting in linear space, On parallel integer sorting

Cites Work

• Sorting in \(c \log n\) parallel steps
• Parallel computation and conflicts in memory access
• Axioms and hulls
• Deterministic coin tossing with applications to optimal parallel list ranking
• A universal interconnection pattern for parallel computers
• Design and implementation of an efficient priority queue
• Fast parallel sorting algorithms
• Implementation of simultaneous memory address access in models that forbid it