Deterministic parallel selection algorithms on coarse-grained multicomputers

摘要

We present two deterministic parallel Selection algorithms for distributed memory machines, under the coarse-grained multicomputer model. Both are based on the use of two weighted 3-medians, that allows discarding at least 1/3 of the elements in each iteration. The first algorithm slightly improves the current experimentally fastest algorithm by Saukas and Song where at least 1/4 of the elements are discarded in each iteration, while the second one is a fast, special purpose algorithm working for a particular class of input, namely an input that can be sorted in linear time using RadixSort.