Splaysort versus Cartesian tree sort

A comparison sorting algorithm is called adaptive if its performance can be better than the worst-case \( O(n\log n) \) time for comparison sorting algorithms, on subsets of inputs that are somehow close to being already sorted. Two examples of this are a Cartesian tree based sorting algorithm described by Levcopoulos and Petersson in WADS 1989, and splaysort, a splay tree based sorting algorithm described by Moffat, Eddy, and Petersson in Software: Practice and Experience 1996. How do these two algorithms compare with each other?

First, let's describe the algorithms in a little more detail. Cartesian tree sort is at heart a form of selection sort, an algorithm that finds the elements of the output sequence in their sorted order, using data structures to speed up how it finds each element. It builds a Cartesian tree on the input, a tree in which the parent of each value is the larger of the two nearest smaller values on either side of it; this can be done in linear time. It maintains a binary heap of active values, initially just the root of the Cartesian tree. And then it repeatedly moves the smallest element of the heap to the output list, replacing it in the heap by its children in the Cartesian tree.

Its running time can be understood in terms of the following diagram, which I drew for Wikipedia a few years ago. It shows a plot of a data set for a sorting problem in which the horizontal axis represents the input sorted order and the vertical axis represents the value to be sorted (or equivalently, since the vertical scale is unimportant, the position in the output sorted order). For any input item \( x \) (such as the one highlighted by the dark blue color in the figure) one can draw a horizontal line through this plot, which cuts through several other edges (red in the figure). The red edges are called "bracketing pairs" and they represent pairs of consecutive inputs that sandwich \( x \). At the time \( x \) is pulled from the heap in the Cartesian tree sorting algorithm, the size of the heap is proportional to the number of bracketed pairs. Thus, the cost for processing \( x \) is proportional to the logarithm of its number of bracketed pairs, and adding this over the whole input gives the time for the whole algorithm. This is tight to within constant factors, for all inputs, not just an upper bound. For inputs in which the average number of bracketed pairs is significantly less than the input length, the time will be significantly less than \( O(n\log n) \).

Splaysort, on the other hand, is a form of insertion sort, in which we add items one by one to a sorted list, using some data structures to make each addition fast. In splay sort, the data structure is a splay tree, used as a binary search tree on the already-processed input items. The time bounds for splay trees are not well understood (in particular, we don't know whether they are within a constant factor of every other binary search tree balancing strategy for every possible input — this is the famous dynamic optimality conjecture) but some upper bounds are known. One such bound is the finger theorem, proven by Cole in STOC 1990, which states that the time to access an item in a splay tree is at most proportional to the logarithm of the number of items that separate it from the previously accessed item.

We can use Cole's bound to give an adaptive analysis of splaysort. Again, consider the diagram above, with the horizontal axis giving the position of a value in the input and the vertical axis (which matters for this part of the analysis) giving the position in the sorted output rather than its numerical value. Using Cole's bound, the cost of inserting each item into the splay tree is at most proportional to the logarithm of the length of the edge connecting it to the previous item. The time for the whole splaysort algorithm is at most the sum of the logs of the edge lengths.

Theorem: Splay sort is competitive with Cartesian tree sort, meaning that the time for splay sort is at most a constant times the time for Cartesian tree sort.

It's not hard to find inputs for which the two algorithms have differing time complexities. For instance, take a sorted sequence of \( n \) values, pull off the top and bottom \( n/\log n \) of them and riffle them together, then concatenate the rest of the values in sorted order after the riffled set. Most of the items in the resulting sequence will have \( 2n/\log n \) bracketed pairs, causing the Cartesian tree algorithm to take \( \Theta(n\log n) \) time on this input. However, the number of long edges in the diagram is small enough to make the time for splaysort remain linear. Thus, splaysort is strictly stronger, as an adaptive algorithm, than Cartesian tree sort: it is always within a constant factor of the same running time, and sometimes much faster.

The dynamic optimality conjecture implies that splaysort is competitive with other binary-tree based insertion sorts, but it doesn't seem to say much about its competitiveness against other sorting algorithms such as selection sorts or merge sorts. It's not possible for splaysort to be competitive against all comparison sorting algorithms: for instance, let \( X \) be an input permutation on which splaysort is slow, and devise a comparison sorting algorithm that tests whether the input is of type \( X \), if so handles it in linear time, and if not reverts to some other algorithm. But is there a natural and generally useful adaptive sorting algorithm that splaysort is not competitive against? I don't know of one.

---

Comments: