Probabilistic Parallel Algorithms for Sorting and Selection
Rüdiger Reischuk · SIAM Journal on Computing · 1985
Probabilistic parallel algorithms are described to sort n keys and to select the k-smallest element among them. For each problem we construct a probabilistic parallel decision tree. The tree for selection finishes with high probability in constant time and the sorting tree in time $O(\log n)$. The same time bound for sorting can also be achieved by a probabilistic parallel machine consisting of n RAMs, each with small private memory, and a common memory of size $O(n)$. These algorithms meet the information theoretic lower bounds.