Optimal parallel quicksort on EREW PRAM

Weixiong Zhang; Nageswara S.V. Rao

doi:10.1007/BF01952784

Optimal parallel quicksort on EREW PRAM

Weixiong Zhang, Nageswara S.V. Rao

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

3 Scopus citations

Abstract

In this paper, we present parallel quicksort algorithms running in O((n/p+log p) log n) expected time and O((n/p+log p+log log n) log n) deterministic time respectively, and both with O(n) space by using p processors on EREW PRAM. When p=O(n/log n), the cost is optimal, in terms of the product of time and number of processors. These algorithms can be used to obtain parallel algorithms for constructing balanced binary search trees without using sorting algorithms. One of our quicksort algorithms leads to a parallel quickhull algorithm on EREW PRAM.

Original language	English
Pages (from-to)	69-74
Number of pages	6
Journal	BIT
Volume	31
Issue number	1
DOIs	https://doi.org/10.1007/BF01952784
State	Published - Mar 1991
Externally published	Yes

Keywords

E. 1
EREW PRAM
F. 2.2.
binary search tree
parallel algorithms
quickhull
quicksort

Access to Document

10.1007/BF01952784

Cite this

@article{2375e48ccf8c4428a0b3578a342e6763,

title = "Optimal parallel quicksort on EREW PRAM",

abstract = "In this paper, we present parallel quicksort algorithms running in O((n/p+log p) log n) expected time and O((n/p+log p+log log n) log n) deterministic time respectively, and both with O(n) space by using p processors on EREW PRAM. When p=O(n/log n), the cost is optimal, in terms of the product of time and number of processors. These algorithms can be used to obtain parallel algorithms for constructing balanced binary search trees without using sorting algorithms. One of our quicksort algorithms leads to a parallel quickhull algorithm on EREW PRAM.",

keywords = "E. 1, EREW PRAM, F. 2.2., binary search tree, parallel algorithms, quickhull, quicksort",

author = "Weixiong Zhang and Rao, {Nageswara S.V.}",

year = "1991",

month = mar,

doi = "10.1007/BF01952784",

language = "English",

volume = "31",

pages = "69--74",

journal = "BIT",

issn = "0006-3835",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - Optimal parallel quicksort on EREW PRAM

AU - Zhang, Weixiong

AU - Rao, Nageswara S.V.

PY - 1991/3

Y1 - 1991/3

N2 - In this paper, we present parallel quicksort algorithms running in O((n/p+log p) log n) expected time and O((n/p+log p+log log n) log n) deterministic time respectively, and both with O(n) space by using p processors on EREW PRAM. When p=O(n/log n), the cost is optimal, in terms of the product of time and number of processors. These algorithms can be used to obtain parallel algorithms for constructing balanced binary search trees without using sorting algorithms. One of our quicksort algorithms leads to a parallel quickhull algorithm on EREW PRAM.

AB - In this paper, we present parallel quicksort algorithms running in O((n/p+log p) log n) expected time and O((n/p+log p+log log n) log n) deterministic time respectively, and both with O(n) space by using p processors on EREW PRAM. When p=O(n/log n), the cost is optimal, in terms of the product of time and number of processors. These algorithms can be used to obtain parallel algorithms for constructing balanced binary search trees without using sorting algorithms. One of our quicksort algorithms leads to a parallel quickhull algorithm on EREW PRAM.

KW - E. 1

KW - EREW PRAM

KW - F. 2.2.

KW - binary search tree

KW - parallel algorithms

KW - quickhull

KW - quicksort

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

U2 - 10.1007/BF01952784

DO - 10.1007/BF01952784

M3 - Article

AN - SCOPUS:0040648512

SN - 0006-3835

VL - 31

SP - 69

EP - 74

JO - BIT

JF - BIT

IS - 1

ER -

Optimal parallel quicksort on EREW PRAM

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this