A TREE-BASED MERGESORT

Authors
MOFFAT A PETERSSON O WORMALD NC
Citation
A. Moffat et al., A TREE-BASED MERGESORT, Acta informatica, 35(9), 1998, pp. 775-793
Citations number
13
Categorie Soggetti
Computer Science Information Systems","Computer Science Information Systems
Journal title
Acta informatica → ACNP
ISSN journal
00015903
Volume
35
Issue
9
Year of publication
1998
Pages
775 - 793
Database
ISI
SICI code
0001-5903(1998)35:9<775:>2.0.ZU;2-T
Abstract
We demonstrate that if standard Mergesort is implemented using finger search trees instead of arrays it optimally adapts to a set of measure s of presortedness not fulfilled by any other algorithm.