In this paper we present efficient deterministic and randomized algori
thms for selection on any interconnection network when the number of i
nput keys (n) is greater than or equal to the number of processors (p)
. Our deterministic algorithm runs on any network in time O(n/p log lo
g p + T-p(s) log n), where T-p(s) is the time needed for sorting p key
s using p processors, On the other hand, our randomized algorithm runs
in an expected time of O((n/p + T-p(sparse)) log log p) on any networ
k, where T-p(sparse) is the time needed for collecting and sorting p(1
-epsilon) sample keys using p processors, (Here epsilon is a constant
<1). Application of the above algorithms on the mesh and the hypercube
yields better results than known before, We have implemented our rand
omized algorithm on the Connection Machine CM2. Experimental results o
btained are promising, In this paper we also report our implementation
details. (C) 1997 Academic Press.