Parallel merge sort

Richard Cole

doi:10.1137/0217049

Parallel merge sort

Richard Cole

Computer Science

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	770-785
Number of pages	16
Journal	SIAM Journal on Computing
Volume	17
Issue number	4
DOIs	https://doi.org/10.1137/0217049
State	Published - 1988

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1137/0217049

Cite this

@article{c615f5eac6164fc6bb17d6118ff6c326,

title = "Parallel merge sort",

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

author = "Richard Cole",

year = "1988",

doi = "10.1137/0217049",

language = "English (US)",

volume = "17",

pages = "770--785",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "4",

}

TY - JOUR

T1 - Parallel merge sort

AU - Cole, Richard

PY - 1988

Y1 - 1988

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

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

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

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

U2 - 10.1137/0217049

DO - 10.1137/0217049

M3 - Article

AN - SCOPUS:0024057356

SN - 0097-5397

VL - 17

SP - 770

EP - 785

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 4

ER -

Parallel merge sort

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this