TY - GEN
T1 - Sorting and/by merging finger trees
AU - Moffat, Alistair
AU - Petersson, Ola
AU - Wormald, Nicholas C.
PY - 1992
Y1 - 1992
N2 - We describe a sorting algorithm that is optimally adaptive with respect to several important measures of presortedness. In particular, the algorithm requires O(n log(k/n)) time on sequences with k inversions; O(n-F k log k) time on sequences X that have a longest ascending subsequence of length n - k and for which Rera(X) = k; and O(nlog k) time on sequences that can be decomposed into k monotone shuffles. The algorithm makes use of an adaptive merging operation implemented using finger search trees.
AB - We describe a sorting algorithm that is optimally adaptive with respect to several important measures of presortedness. In particular, the algorithm requires O(n log(k/n)) time on sequences with k inversions; O(n-F k log k) time on sequences X that have a longest ascending subsequence of length n - k and for which Rera(X) = k; and O(nlog k) time on sequences that can be decomposed into k monotone shuffles. The algorithm makes use of an adaptive merging operation implemented using finger search trees.
UR - http://www.scopus.com/inward/record.url?scp=85015178122&partnerID=8YFLogxK
U2 - 10.1007/3-540-56279-6_102
DO - 10.1007/3-540-56279-6_102
M3 - Conference Paper
AN - SCOPUS:85015178122
SN - 9783540562795
VL - 650 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 499
EP - 508
BT - Algorithms and Computation - 3rd International Symposium, ISAAC 1992, Proceedings
PB - Springer-Verlag London Ltd.
T2 - 3rd International Symposium on Algorithms and Computation, ISAAC 1992
Y2 - 16 December 1992 through 18 December 1992
ER -