Parallel merge sort

Research output: Contribution to journalArticle

Abstract

We give a parallel implementation of merge sort on a CREW PRAM that uses n processors and O(log n) time; the constant in the running time is small. We also give a more complex version of the algorithm for the EREW PRAM; it also uses n processors and O(log n) time. The constant in the running time is still moderate, though not as small.

Original languageEnglish (US)
Pages (from-to)770-785
Number of pages16
JournalSIAM Journal on Computing
Volume17
Issue number4
DOIs
StatePublished - Jan 1 1988

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Parallel merge sort'. Together they form a unique fingerprint.

  • Cite this