A Tree-based Mergesort

Alistair Moffat
Department of Computer Science, The University of Melbourne, Parkville 3052, Australia.

Ola Petersson
Department of Computer Science, Lund University, Box 118, S-221 00 Lund, Sweden; and Department of Mathematics, Statistics, and Computer Science, Vaxjo University, S-351 95 Vaxjo, Sweden.

Nicholas C. Wormald
Department of Mathematics, The University of Melbourne, Parkville 3052, Australia.

Status

Acta Informatica, 35(9):775-793, August 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.