Assume as given a set S of n positive integers (or more generally, any totally ordered set); e.g., S = { e ₁ , e ₂ , . . . , e _n }. For example, suppose S is already sorted, i.e., e ₁ < e ₂ < . . . < e _n. Then we say e ₁ is the smallest element and for 1 ≤ k ≤ n we say e _k is the k^th smallest element. Next, let S be a set which is not necessarily sorted. Suppose we have fewer processors than n, say the number of parallel processors is n ^a where a ∈ [0,1]. That is a = log _n N _p where N _p is the number of parallel processors. The author presents a parallel algorithm for selecting the K^th smallest element of S which runs in O ( n ^{1 − a} ) time and has an optimal total cost of n ^a O ( n ^{1 − a} ) = O ( n ).

The author points out an open problem: “Is there an algorithm for parallel selection which for some s ∈ [0,1] uses O ( n / ( log n ) ^s ) processors and runs in O ( log n ) ^s time?” The author mentions two applications:

(1) A parallel version of Quicksort (see Knuth [1]) which uses n^a processors to sort n items and runs in O ( n ^{1 − a} log n ) time.

(2) A parallel adaptation of an algorithm due to Kirkpatrick and Seidel [2] for finding the convex hull of a set of n points in the plane. The parallel algorithm uses n ^a processors and runs in O ( n ^{1 − a} log N _e ) time where N _e is the number of edges on the convex hull. Both of the applications algorithms are cost optimal.