Constant time parallel sorting: An empirical view.

DOI10.1016/S0022-0000(03)00040-0MaRDI QIDQ1401981zbMATH OpenOpenAlexFDO

Authors William Gasarch, Evan Golub, Clyde 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)

Recommendations

• Sorting in rounds
• Communication-Efficient Parallel Sorting
• scientific article; zbMATH DE number 1256741
• An optimal parallel algorithm for sorting multisets
• Sorting, Approximate Sorting, and Searching in Rounds

Cites work

• A survey of constant time parallel sorting
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Expanders that beat the eigenvalue bound: Explicit construction and applications
• Explicit Concentrators from Generalized N-Gons
• Extracting all the randomness and reducing the error in Trevisan's extractors
• Extracting Randomness via Repeated Condensing
• scientific article; zbMATH DE number 4152425 (Why is no real title available?)
• scientific article; zbMATH DE number 3928360 (Why is no real title available?)
• scientific article; zbMATH DE number 3708485 (Why is no real title available?)
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• Parallel sorting
• Parallel Sorting with Constant Time for Comparisons
• Parallelism in Comparison Problems
• Ramanujan graphs
• Randomness is linear in space
• Sorting and Merging in Rounds
• Sorting and Selecting in Rounds
• Sorting in one round
• Sorting in rounds
• Sorting, Approximate Sorting, and Searching in Rounds

Cited in

(2)

• Constant-time sorting
• Finding an unknown acyclic orientation of a given graph

This page was built for publication: Constant time parallel sorting: An empirical view.

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