Tight Comparison Bounds on the Complexity of Parallel Sorting

DOI10.1137/0216032zbMath0654.68070OpenAlexW2025558913MaRDI QIDQ3801082

Uzi Vishkin, Yossi Azar

Publication date: 1987

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

Full work available at URL: https://semanticscholar.org/paper/9b1746318f760635214bfd001fcaed1b0530f2a6

zbMATH Keywords

parallel computationlower boundsparallel sortingsorting networkbounded parallelismAKS network

Mathematics Subject Classification ID

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

Related Items

Transforming comparison model lower bounds to the parallel-random-access-machine, Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems, Unnamed Item, Sorting roughly sorted sequences in parallel, Parallel selection, Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm, Randomized range-maxima in nearly-constant parallel time, The average-case parallel complexity of sorting, Counting clique trees and computing perfect elimination schemes in parallel, Parallel comparison merging of many-ordered lists, Parallel comparison algorithms for approximation problems