Parallel selection

Abstract

Using the parallel comparison tree model of Valiant, we study the time required in the worst case to select the median of n elements with p processors. With a miniscule improvement of recent work by Ajtai, Komlós, Steiger and Szemerédi, we show that it is Θ n p+log logn log(1+ p n) for 1≤p≤( n 2). This expression is equivalent to one established by Kruskal as the time required to merge two lists of n/2 elements with p processors and, rather curiously, includes as a sub-expression Θ logn log(1+ p n) established by Azar and Vishkin as the time required to sort n elements with p processors. © 1990.