Constant time parallel sorting: An empirical view.

DOI10.1016/S0022-0000(03)00040-0zbMath1054.68039OpenAlexW2058512113MaRDI QIDQ1401981

William I. Gasarch, Evan Golub, Clyde P. Kruskal

Publication date: 19 August 2003

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(03)00040-0

zbMATH Keywords

non-constructive algorithms

Mathematics Subject Classification ID

Searching and sorting (68P10) Parallel algorithms in computer science (68W10)

Related Items

Finding an Unknown Acyclic Orientation of a Given Graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Ramanujan graphs
• Sorting in rounds
• Expanders that beat the eigenvalue bound: Explicit construction and applications
• Sorting in one round
• Parallel sorting
• Randomness is linear in space
• Explicit Concentrators from Generalized N-Gons
• Sorting and Selecting in Rounds
• Sorting, Approximate Sorting, and Searching in Rounds
• Parallel Sorting with Constant Time for Comparisons
• Sorting and Merging in Rounds
• Parallelism in Comparison Problems
• Extracting Randomness via Repeated Condensing
• Extracting all the randomness and reducing the error in Trevisan's extractors