A parallel bucket sort

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


The problem to sort integers on a parallel RAM (PRAM) is investigated. An algorithm sorting n integers on n/log n processors in expected time O(log n) is presented. It is a parallel version of the bucket sort. The simultaneous resource bounds of this algorithm are asymptotically optimal.

Original languageEnglish (US)
Pages (from-to)57-61
Number of pages5
JournalInformation Processing Letters
Issue number2
StatePublished - Feb 29 1988
Externally publishedYes


  • Analysis of algorithms
  • integer sorting
  • optimal parallel algorithm

ASJC Scopus subject areas

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


Dive into the research topics of 'A parallel bucket sort'. Together they form a unique fingerprint.

Cite this