Running time of the Treapsort algorithm
We analyse the running time of Treapsort, a sorting algorithm in the MOQA(1) programming language, which acts on treaps. We show that, using the 'partial permutation' model of Banderier et al. (2003) [1], Treapsort has smoothed complexity Theta (sigma(-1)n ln n) 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. (C) 2013 Elsevier B.V. All rights reserved.
sorting algorithms smoothed complexity average-case analysis of algorithms moqa