SPLAYSORT - FAST, VERSATILE, PRACTICAL

Adaptivity in sorting algorithms is sometimes gained at the expense of practicality, We give experimental results showing that Splaysort - s orting by repeated insertion into a Splay tree - is a surprisingly eff icient method for in-memory sorting, Splaysort appears to be adaptive with respect to all accepted measures of presortedness, and it outperf orms Quicksort for sequences with modest amounts of existing order, Al though Splaysort has a linear space overhead, there are many applicati ons for which this is reasonable, In these situations Splaysort is an attractive alternative to traditional comparison-based sorting algorit hms such as Heapsort, Mergesort, and Quicksort.