(Mis)applications of randomization to sorting: slower than slow

John Howat, School of Computer Science, Carleton

We present a sorting algorithm that has a slightly suboptimal expected running time of $\Omega(n \times n!)$. An easily accessible analysis (due to Gruber, Holzer and Ruepp) is discussed and we bound the best, worst and average number of comparisons and swaps performed by the algorithm. This talk will concentrate primarily on techniques for the analysis of randomized algorithms.