2010/06/21 by Vasileios Iliopoulos, Iliopoulos, Vasileios, David Penman +1
Computer Science · Mathematics · #Algorithms and Data Compression #FOS: Mathematics #Probability (math.PR) #math.PR
paper · pdf · doi:10.48550/arxiv.1006.4063
20 pages. We do not intend to submit this elsewhere
arxiv created 2010/06/21 · openalex publication_date 2010/06/21 · arxiv updated 2010/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper gives a straightforward self-contained proof of the formula for the variance of the number of comparisons used by the Quicksort sorting algorithm when pivots are chosen uniformly at random. The result has been known for some time but we had not found a single source giving all details of the argument in a self-contained and explicit way. We hope these details may be of interest to students and others wishing to understand this calculation. No originality is claimed for the result.