We present upper bounds for sorting and selecting the median in a fixed number of rounds. These bounds match the known lower bounds to within logarithmic factors. They also have the merit of being “explicit modulo expansion”; that is, probabilistic arguments are used only to obtain expanding graphs, and when explicit constructions for such graphs are found, explicit algorithms for sorting and selecting will follow. Using the best currently available explicit constructions for expanding graphs, we present the best currently known explicit algorithms for sorting and selecting in rounds.
© 1987 Society for Industrial and Applied Mathematics
Nicholas Pippenger. "Sorting and Selecting in Rounds", Society for Industrial and Applied Mathematics Journal on Computing, 16, 1032 (1987).