Splaysort: Fast,Versatile, Practical |
| |
Authors: | Alistair Moffat Gary Eddy Ola Petersson |
| |
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. |
| |
Keywords: | adaptive sorting splay tree splaytree quicksort natural merge sort |
|
|