A randomized sorting algorithm on the BSP model

DOI10.1142/S179383091450061XMaRDI QIDQ2931927zbMATH OpenOpenAlexFDO

Authors A. V. Gerbessiotis, C. 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) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Searching and sorting (68P10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Parallel sorting by regular sampling
• Probabilistic Parallel Algorithms for Sorting and Selection
• Communication-Efficient Parallel Sorting
• scientific article; zbMATH DE number 1256741
• Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms

Cites work

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

Cited in

(2)

• Power balance and apportionment algorithms for the United States Congress
• An architecture independent study of parallel segment trees

This page was built for publication: A randomized sorting algorithm on the BSP model

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