Perfect simulation from the Quicksort limit distribution

2000/05/23 by Luc Devroye, Devroye, Luc, James Allen Fill +3
Computer Science · Mathematics · #11K45 (secondary) #65C05 #65C10 (primary) #68U20 #Algorithms and Data Compression #Cellular Automata and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Numerical Methods and Algorithms #Probability (math.PR) #cs.DS #math.PR #msc:11K45 #msc:65C05 #msc:65C10 #msc:68U20

paper · pdf · doi:10.48550/arxiv.math/0005237

7 pages. See also http://www.mts.jhu.edu/~fill/, http://www-cgrl.cs.mcgill.ca/~luc/, and http://www.stochastik.uni-freiburg.de/homepages/neininger/ . Submitted for publication in May, 2000

arxiv created 2000/05/23 · openalex publication_date 2000/05/23 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The weak limit of the normalized number of comparisons needed by the Quicksort algorithm to sort n randomly permuted items is known to be determined implicitly by a distributional fixed-point equation. We give an algorithm for perfect random variate generation from this distribution.

Related

• Approximating the limiting Quicksort distribution
• Randomized QuickSort and the Entropy of the Random Source
• Variance of the number of Comparisons of Randomized Quicksort
• Refined Quicksort asymptotics
• The limiting distribution for the number of symbol comparisons used by QuickSort is nondegenerate (extended abstract)