A randomized sorting algorithm on the BSP model

DOI10.1142/S179383091450061XzbMath1307.68033OpenAlexW2110776243MaRDI QIDQ2931927

Alexandros V. Gerbessiotis, Constantinos J. Siniolakis

Publication date: 28 November 2014

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s179383091450061x

zbMATH Keywords

random samplingoversamplingBSP modellatency-tolerant algorithmsrandomized sorting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

An architecture independent study of parallel segment trees

Cites Work

• Unnamed Item
• Unnamed Item
• Ordered \(h\)-level graphs on the BSP model
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Parallel sorting by regular sampling
• A randomized parallel sorting algorithm with an experimental study
• Architecture independent parallel selection with applications to parallel priority queues
• Tight Bounds on the Complexity of Parallel Sorting
• Probabilistic Parallel Algorithms for Sorting and Selection
• Parallel Merge Sort
• Parallel permutation and sorting algorithms and a new generalized connection network
• Cubesort: A parallel algorithm for sorting N data items with S-sorters
• Communication-Efficient Parallel Sorting
• Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms
• Samplesort: A Sampling Approach to Minimal Storage Tree Sorting