Parallel Selection

Document Type



Mathematics (HMC)

Publication Date



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.

Rights Information

© 1990 Elsevier Ltd.

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.