A Parallel Median Algorithm

Richard Cole, Chee-Keng Yap

Abstract

We give a deterministic algorithm for finding the kth smallest item in a set of n items, running in O((log log n)2) parallel time on O(n) processors in Valiant's comparison model.
BibTeX
@article{cole1985parallel,
  author = {Richard Cole and Chee-Keng Yap},
  title = {{A Parallel Median Algorithm}},
  journal = {Inf. Process. Lett.},
  year = {1985},
  doi = {10.1016/0020-0190(85)90080-8},
}

Loading related content...

Figure