Tight Comparison Bounds on the Complexity of Parallel Sorting

DOI10.1137/0216032zbMATH Open0654.68070OpenAlexW2025558913MaRDI QIDQ3801082FDOQ3801082

Authors: 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

Recommendations

• Tight Bounds on the Complexity of Parallel Sorting
• The Complexity of Parallel Sorting
• Sorting in rounds
• The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms
• The average-case parallel complexity of sorting

zbMATH Keywords

lower boundsparallel computationsorting networkparallel sortingbounded parallelismAKS network

Mathematics Subject Classification ID

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

Cited In (25)

• The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms
• The Complexity of Parallel Sorting
• Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems
• Title not available (Why is that?)
• Deterministic sorting in nearly logarithmic time on the hypercube and related computers
• Sorting in rounds
• Asymptotically Tight Bounds for Performing BMMC Permutations on Parallel Disk Systems
• Comparing algorithms for sorting with \(t\) stacks in series
• Transforming comparison model lower bounds to the parallel-random-access-machine
• Title not available (Why is that?)
• Peculiarities of the parallel sorting algorithm with rank formation
• The average-case parallel complexity of sorting
• Parallel comparison algorithms for approximation problems
• Parallel complexity of sorting problems
• Parallel selection
• Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm
• Space and time complexities of balanced sorting on processor arrays
• A tighter upper bound on the worst case behavior of Conway's parallel sorting algorithm
• Sorting roughly sorted sequences in parallel
• Randomized range-maxima in nearly-constant parallel time
• Counting clique trees and computing perfect elimination schemes in parallel
• Title not available (Why is that?)
• Parallel comparison merging of many-ordered lists
• Tight Bounds on the Complexity of Parallel Sorting
• On Parallel Searching

This page was built for publication: Tight Comparison Bounds on the Complexity of Parallel Sorting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3801082)