TY - GEN
T1 - More efficient parallel integer sorting
AU - Han, Yijie
AU - He, Xin
PY - 2012
Y1 - 2012
N2 - We present a more efficient CREW PRAM algorithm for integer sorting. This algorithm sorts n integers in { 0, 1, 2, ..., n 1/2} in O((logn) 3/2/loglogn) time and O(n (logn/loglogn) 1/2) operations. It also sorts n integers in {0, 1, 2,..., n-1} in O((logn) 3/2/ loglogn) time and O(n (logn/loglogn) 1/2logloglogn) operations. Previous best algorithm [13] on both cases has time complexity O(logn) but operation complexity O(n(logn) 1/2).
AB - We present a more efficient CREW PRAM algorithm for integer sorting. This algorithm sorts n integers in { 0, 1, 2, ..., n 1/2} in O((logn) 3/2/loglogn) time and O(n (logn/loglogn) 1/2) operations. It also sorts n integers in {0, 1, 2,..., n-1} in O((logn) 3/2/ loglogn) time and O(n (logn/loglogn) 1/2logloglogn) operations. Previous best algorithm [13] on both cases has time complexity O(logn) but operation complexity O(n(logn) 1/2).
KW - Algorithms
KW - bucket sorting
KW - design of algorithms
KW - integer sorting
KW - PRAM algorithms
UR - https://www.scopus.com/pages/publications/84861208336
U2 - 10.1007/978-3-642-29700-7_26
DO - 10.1007/978-3-642-29700-7_26
M3 - Conference contribution
AN - SCOPUS:84861208336
SN - 9783642296994
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 279
EP - 290
BT - Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2012, Proceedings
T2 - 6th International Frontiers of Algorithmics Workshop, FAW 2012 and 8th International Conference on Algorithmic Aspects of Information and Management, AAIM 2012
Y2 - 14 May 2012 through 16 May 2012
ER -