Running time of the Treapsort algorithm

We analyse the running time of Treapsort, a sorting algorithm in the MOQA1, programming language, which acts on treaps. We show that, using the ‘partial permutation’ model of Banderier et al. (2003) [1], Treapsort has smoothed complexity Θ(σ−1nlnn) for treaps of size n. We also show that the multiset of running times of Treapsort on all treaps of size n is equal to the multiset of running times of Quicksort on all lists of length n.