Efficient parallel algorithms for selection and multiselection on mesh-connected computers

In this paper we present a set of efficient parallel algorithms for selection and multiselection on a √p×√p mesh-connected computer. Our main contributions include: a new algorithm for single-element selection for the general case when p⩽n based on the generalized bitonic selection approach, which is more efficient than the previously known result for this problem when p⩾n^1/2+ε for any ε>0; an efficient algorithm for multiselection on SIMD mesh for selecting r elements from n given elements; an efficient algorithm for multiselection on an MIMD mesh that runs in O(logr(p^1/2+n/p(log² p)) time and is time-optimal w.r.t. the current best result on single-element selection on mesh