Journal article
A tree-based Mergesort
A Moffat, O Petersson, NC Wormald
Acta Informatica | SPRINGER VERLAG | Published : 1998
Abstract
We demonstrate that if standard Mergesort is implemented using finger search trees instead of arrays it optimally adapts to a set of measures of presortedness not fulfilled by any other algorithm.