Splaysort: fast, versatile, practical

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.