UNIFYING THEMES FOR SELECTION ON ANY NETWORK

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.