Splay Sort

Do a sequence of inserts, then traverse the resulting tree. How?

Running time: Clearly O(n²). Why?

We will see, in fact, that any sequence of k splays on a tree with n nodes runs in $O(k \log n)$. Amazing!

We will use potential functions and amortized analysis to show this.

Therefore, what is splay sort's running time?