First Written: March 8, 2019

One of the greatest algorithms of all time is Quicksort, (it is ranked 7th in this top 10 list). Its average running time is famously O(n log(n)), and its variance, less famously, is O(n²) (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.

Added March 12, 2019: Helmut Prodinger pointed our attention to this human-generated gem.

Added March 22, 2019: Sumit Kumar Jha pointed our attention to yet another human-generated gem.

Maple package

• QuickSortAnalysis.txt, a Maple package to analyze the random variable "running time of quicksort".

Sample Input and Output for QuickSortAnalsis.txt

• If you want to see the first 130 terms in the sequence of probablity generating functions of the random variable "Number of comparisons in Quicksort with lists of length n"

  the input file generates the output file.

• If you want to see the the probablity generating function of the random variable "Number of comparisons in Quicksort with lists of length 150, in floating point

  the input file generates the output file.

• If you want to see explicit expressionf or the first eight moments of the random variable "Number of comparisons in Quicksort with lists of length n" as a function of n, as well as their asympotic expressions and scaled limits

  the input file generates the output file.

• If you want to see a computer-generated article about the above

  the input file generates the output file.

• If you want to see a the approximate percentiles for the running time of Quicksort with a list with 10000 items

  the input file generates the output file.

• If you want to see a the results of simulating quicksort on 10000 randomly chosen sequences of length 200, and also the theoretical values of the expectation, variance, skewness, and kurtosis,

  the input file generates the output file.

• If you want to see a the results of simulating quicksort on 50000 randomly chosen sequences of length 200, and also the theoretical values of the expectation, variance, skewness, and kurtosis,

  the input file generates the output file.

Pictures

• Here is the diagram of the the scaled probability density function for the running time of quicksort for lists of length 130

• Here is the diagram of the approximate the cumulative probability function for the running time of quicksort for lists of length 10000

Doron Zeilberger's Home Page