Deterministic sorting and randomized median finding on the BSP model
- 1 January 1996
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 223-232
- https://doi.org/10.1145/237502.237561
Abstract
We present new BSP algorithms for deterministic sortingand randomized median finding. We sort n general keys byusing a partitioning scheme that achieves the requirementsof efficiency (one-optimality) and insensitivity against dataskew (the accuracy of the splitting keys depends solely onthe step distance, which can be adapted to meet the worstcaserequirements of our application). Although we employsampling in order to realize efficiency, we can give a preciseworst-case estimation of the ...Keywords
This publication has 0 references indexed in Scilit: