Deterministic selection in O(loglog N) parallel time
Miklós Ajtai, János Komlós, William Steiger, Endre Szemerédi · 1986
We show that in the deterministic comparison model for parallel computation, n processors can select the k th smallest item from a set of n numbers in O(loglogn) parallel time.With this result all comparison tasks (selection, merging, sorting), now have upper and lower bounds of the same order in both random and deterministic models.