Paper Info
Title
An optimal parallel adaptive sorting algorithm
Abstract
We consider the problem of designing optimal parallel algorithms for sorting presorted sequences. To evaluate the existing order in an input sequence, we use the number of the maximal ascending consecutive subsequences, Runs, in the sequence as a measure of presortedness. An adaptive parallel sorting algorithm is presented, which sorts a sequence X of length n in O(log n.log Runs (X)) time by using O(n/log n) processors in the EREW PRAM model of computation. It is the first adaptive parallel sorting algorithm that is cost optimal with respect to Runs.
Year
DOI
Venue
1991
10.1016/0020-0190(91)90179-L
Inf. Process. Lett.
Keywords
Field
DocType
optimal parallel adaptive,parallel algorithms,sorting,sorting algorithm
Computer science,Parallel algorithm,Parallel computing,Algorithm,Sorting,Model of computation,Adaptive algorithm,Parallel sorting,Sorting algorithm
Journal
Volume
Issue
ISSN
39
4
0020-0190
Citations 
PageRank 
References 
3
0.51
14
Authors
2
Name
Order
Citations
PageRank
Svante Carlsson176490.17
Jingsen Chen2669.80