Splaysort

In computer science, splaysort is an adaptive comparison sorting algorithm based on the splay tree data structure.

The steps of the algorithm are:

Thus, the algorithm may be seen as a form of insertion sort or tree sort, using a splay tree to speed up each insertion.

Based on the amortized analysis of splay trees, the worst case running time of splaysort, on an input with n data items, is O(n log n), matching the time bounds for efficient non-adaptive algorithms such as quicksort, heap sort, and merge sort.

For an input sequence in which most items are placed close to their predecessor in the sorted order, or are out of order with only a small number of other items, splaysort can be faster than O(n log n), showing that it is an adaptive sort. To quantify this, let d_x be the number of positions in the input that separate x from its predecessor, and let i_x be the number of items that appear on one side of x in the input and on the other side of x in the output (the number of inversions that involve x). Then it follows from the dynamic finger theorem for splay trees that the total time for splaysort is bounded by

and by

Splaysort can also be shown to be adaptive to the entropy of the input sequence.

In experiments by Moffat, Eddy & Petersson (1996), splaysort was slower than quicksort on tables of random numbers by a factor of 1.5 to 2, and slower than mergesort by smaller factors. For data consisting of larger records, again in a random order, the additional amount of data movement performed by quicksort significantly slowed it down compared to pointer-based algorithms, and the times for splaysort and mergesort were very close to each other. However, for nearly presorted input sequences (measured in terms of the number of contiguous monotone subsequences in the data, the number of inversions, the number of items that must be removed to make a sorted subsequence, or the number of non-contiguous monotone subsequences into which the input can be partitioned) splaysort became significantly more efficient than the other algorithms.

...
Wikipedia