PARALLEL MERGE SORT.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A parallel implementation of merge sort on a CREW PRAM (concurrent-read exclusive-write parallel random access machine) is given that uses n processors and O(log n) time; the constant in the running time is small. Also given is a more complex version of the algorithm for the EREW (exclusive-read exclusive-write) 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)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE
Pages511-516
Number of pages6
ISBN (Print)0818607408, 9780818607400
DOIs
StatePublished - 1986

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

ASJC Scopus subject areas

  • Hardware and Architecture

Cite this