PARALLEL MERGE SORT.

Richard Cole

doi:10.1109/SFCS.1986.41

PARALLEL MERGE SORT.

Richard Cole

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Annual Symposium on Foundations of Computer Science (Proceedings)
Pages	511-516
Number of pages	6
DOIs	https://doi.org/10.1109/SFCS.1986.41
State	Published - 1986

Publication series

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

ASJC Scopus subject areas

Hardware and Architecture

Access to Document

10.1109/SFCS.1986.41

Cite this

@inproceedings{1aab449509ad480b869a0b3c8d3e7dda,

title = "PARALLEL MERGE SORT.",

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.",

author = "Richard Cole",

year = "1986",

doi = "10.1109/SFCS.1986.41",

language = "English (US)",

isbn = "0818607408",

series = "Annual Symposium on Foundations of Computer Science (Proceedings)",

pages = "511--516",

booktitle = "Annual Symposium on Foundations of Computer Science (Proceedings)",

}

TY - GEN

T1 - PARALLEL MERGE SORT.

AU - Cole, Richard

PY - 1986

Y1 - 1986

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0022880641&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0022880641&partnerID=8YFLogxK

U2 - 10.1109/SFCS.1986.41

DO - 10.1109/SFCS.1986.41

M3 - Conference contribution

AN - SCOPUS:0022880641

SN - 0818607408

SN - 9780818607400

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 511

EP - 516

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

ER -