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 [image of equation]* for [image of equation]. 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 [image of equation] established by Azar and Vishkin as the time required to sort n elements with p processors.
*Image was removed for formatting purposes.
© 1990 Elsevier Ltd.
Yossi Azar, Nicholas Pippenger, Parallel selection, Discrete Applied Mathematics, Volume 27, Issues 1–2, May 1990, Pages 49-58, ISSN 0166-218X, 10.1016/0166-218X(90)90128-Y. (http://www.sciencedirect.com/science/article/pii/0166218X9090128Y)