Sorting and/by merging finger trees

Alistair Moffat, Ola Petersson, Nicholas C. Wormald

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

6 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 3rd International Symposium, ISAAC 1992, Proceedings
PublisherSpringer-Verlag London Ltd.
Number of pages10
Volume650 LNCS
ISBN (Print)9783540562795
Publication statusPublished - 1992
Externally publishedYes
Event3rd International Symposium on Algorithms and Computation, ISAAC 1992 - Nagoya, Japan
Duration: 16 Dec 199218 Dec 1992

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume650 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference3rd International Symposium on Algorithms and Computation, ISAAC 1992

Cite this