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)
Pages511-516
Number of pages6
DOIs
StatePublished - Dec 1 1986

Publication series

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

ASJC Scopus subject areas

  • Hardware and Architecture

Cite this

Cole, R. (1986). PARALLEL MERGE SORT. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 511-516). (Annual Symposium on Foundations of Computer Science (Proceedings)). https://doi.org/10.1109/SFCS.1986.41