A randomized sorting algorithm on the BSP model
From MaRDI portal
Publication:2931927
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
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
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