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.