A randomized sorting algorithm on the BSP model

DOI10.1142/S179383091450061XzbMath1307.68033MaRDI 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 sampling; oversampling; BSP model; latency-tolerant algorithms; randomized sorting

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P10: Searching and sorting

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68W20: Randomized algorithms

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

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