An in-place sorting with O (n log n) comparisons and O (n) Moves

被引：9
作者：
Franceschini, G [1 ]
Geffert, V [1 ]
机构：
[1] Univ Pisa, Dept Comp Sci, I-56127 Pisa, Italy
来源：
44TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 2003年
关键词：
D O I：
10.1109/SFCS.2003.1238198
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O(n log n) element comparisons and O(n) element transports. This solves a long-standing open problem, stated explicitly, e.g., in [J. L Munro and V Raman, Sorting with minimum data movement, J. Algorithms, 13, 374-93, 1992], of whether there exists a sorting algorithm that matches the asymptotic lower bounds on all computational resources simultaneously.
引用
收藏
页码：242 / 250
页数：9
相关论文
共 15 条
[1]   ALGORITHM-245 - TREESORT 3 [M1] [J].
FLOYD, RW .
COMMUNICATIONS OF THE ACM, 1964, 7 (12) :701-701
[2]  
FRANCESCHINI G, 2003, IN PLACE SORTING ALG
[3]   Asymptotically efficient in-place merging [J].
Geffert, V ;
Katajainen, J ;
Pasanen, T .
THEORETICAL COMPUTER SCIENCE, 2000, 237 (1-2) :159-181
[4]  
GEFFERT V, 2002, SORTING O N LOG N CO
[5]  
Itai A., 1981, LECTURE NOTES COMPUT, V115, P417
[6]  
Katajainen J., 1996, Nordic Journal of Computing, V3, P27
[7]   In-place sorting with fewer moves [J].
Katajainen, J ;
Pasanen, TA .
INFORMATION PROCESSING LETTERS, 1999, 70 (01) :31-37
[8]  
Knuth D. E., 1973, The Art of Computer Programming Volume 3, Sorting and Searching, VIII
[9]   Selection from read-only memory and sorting with minimum data movement [J].
Munro, JI ;
Raman, V .
THEORETICAL COMPUTER SCIENCE, 1996, 165 (02) :311-323
[10]  
MUNRO JI, 1992, J ALGORITHMS, V13, P374, DOI 10.1016/0196-6774(92)90045-E
12