A Detailed Analysis of Quicksort Running Time
arXiv:1903.03708
Abstract
One of the greatest algorithms of all time is Quicksort. Its average running time is famously O(nlog(n)), and its variance, less famously, is O(n^2) (hence its standard deviation is O(n)). But what about higher moments? Here we find explicit expressions for the first eight moments, their scaled limits, and we describe how to compute, approximately (but very accurately), percentiles of running time for any list-length
13 pages. Accompanied by a Maple package and output files available from http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/qsort.html