Parallel selection

AbstractUsing 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 Θnp+loglognlog(1+pn) for 1≤p≤(n2). 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 Θlognlog(1+pn) established by Azar and Vishkin as the time required to sort n elements with p processors