About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Discrete Applied Mathematics
Paper
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.