Splaysort: Fast, Versatile, Practical
Alistair Moffat
Department of Computer Science,
The University of Melbourne,
Parkville 3052, Australia.
Gary Eddy
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,
V\"{a}xj\"{o} University,
S-351 95 V\"{a}xj\"{o},
Sweden.
Status
Software - Practice & Experience, 126(7):781-797, July 1996.
Abstract
Adaptivity in sorting algorithms is sometimes gained at the expense of
practicality. We give experimental results showing that
Splaysort---sorting by repeated insertion into a Splay tree---is a
surprisingly efficient method for in-memory sorting. Splaysort appears
to be adaptive with respect to all accepted measures of presortedness,
and it outperforms Quicksort for sequences with modest amounts of
existing order. Although Splaysort has a linear space overhead, there
are many applications for which this is reasonable. In these
situations Splaysort is an attractive alternative to traditional
comparison-based sorting algorithms such as Heapsort, Mergesort, and
Quicksort.
Source code
Source code for splaysort is available
here.