AN OPTIMAL PARALLEL ADAPTIVE SORTING ALGORITHM

被引：3
作者：
CARLSSON, S
CHEN, JS
机构：
[1] Department of Computer Science, Lund University, S-221 00 Lund
来源：
INFORMATION PROCESSING LETTERS | 1991年 / 39卷 / 04期
关键词：
PARALLEL ALGORITHMS; SORTING; PRESORTEDNESS;
D O I：
10.1016/0020-0190(91)90179-L
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
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.
引用
收藏
页码：195 / 200
页数：6
相关论文
共 18 条
[1]   SORTING IN C LOG N PARALLEL STEPS [J].
AJTAI, M ;
KOMLOS, J ;
SZEMEREDI, E .
COMBINATORICA, 1983, 3 (01) :1-19
[2]   SORTING ROUGHLY SORTED SEQUENCES IN PARALLEL [J].
ALTMAN, T ;
CHLEBUS, BS .
INFORMATION PROCESSING LETTERS, 1990, 33 (06) :297-300
[3]   ADAPTIVE BITONIC SORTING - AN OPTIMAL PARALLEL ALGORITHM FOR SHARED-MEMORY MACHINES [J].
BILARDI, G ;
NICOLAU, A .
SIAM JOURNAL ON COMPUTING, 1989, 18 (02) :216-228
[4]  
CHEN J, 1991, 2ND P ANN ACM SIAM S, P62
[5]   PARALLEL MERGE SORT [J].
COLE, R .
SIAM JOURNAL ON COMPUTING, 1988, 17 (04) :770-785
[6]   BEST SORTING ALGORITHM FOR NEARLY SORTED LISTS [J].
COOK, CR ;
KIM, DJ .
COMMUNICATIONS OF THE ACM, 1980, 23 (11) :620-624
[7]   SMOOTHSORT, AN ALTERNATIVE FOR SORTING INSITU [J].
DIJKSTRA, EW .
SCIENCE OF COMPUTER PROGRAMMING, 1982, 1 (03) :223-233
[8]   EXPLOITING PARTIAL ORDER WITH QUICKSORT [J].
DROMEY, RG .
SOFTWARE-PRACTICE & EXPERIENCE, 1984, 14 (06) :509-518
[9]   A NEW MEASURE OF PRESORTEDNESS [J].
ESTIVILLCASTRO, V ;
WOOD, D .
INFORMATION AND COMPUTATION, 1989, 83 (01) :111-119
[10]  
Knuth D.E., 1997, ART COMPUTER PROGRAM, V3
12