The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms

DOI10.1137/0217074zbMath0664.68061OpenAlexW2000872165MaRDI QIDQ3815534

Noga Alon, Yossi Azar

Publication date: 1988

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0217074

zbMATH Keywords

parallel sortingcomparison algorithmsrandomized sorting

Mathematics Subject Classification ID

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

Related Items (6)

Search problems: One, two or many rounds ⋮ An average case analysis of a greedy algorithm for the on-line Steiner tree problem ⋮ Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems ⋮ Randomized range-maxima in nearly-constant parallel time ⋮ The average-case parallel complexity of sorting ⋮ The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems

This page was built for publication: The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms