A parallel median algorithm

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)137-139
Number of pages3
JournalInformation Processing Letters
Issue number3
StatePublished - Apr 8 1985


  • Parallel algorithm
  • comparison model
  • median
  • selection

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'A parallel median algorithm'. Together they form a unique fingerprint.

Cite this