Optimal parallel multiselection on EREW PRAM

Multiselection requires to select r elements at specified ranks in a given set of n elements, r ≤ n. This paper proposes a paradigm for parallel multiselection to achieve the optimal cost. Following this paradigm and employing a cost-optimal algorithm for single-element selection, a cost-optimal parallel algorithm for multiselection is presented. Our algorithm runs in O(n^∈; log r) time on an EREW PRAM with n^1-∈ processors for any 0 < ∈ < 1. In the special case when ∈ = log(log n log * n)/log n, our algorithm requires O(log n log * n log r) time and O(n log r) cost.