Probabilistic Parallel Algorithms for Sorting and Selection

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 (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.