2000/05/23 by James Allen Fill, Svante Janson, Fill, James Allen +1
Computer Science · Mathematics · #60E05 #60E10 (secondary) #68P10 #68W40 (primary) #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Cellular Automata and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #cs.DS #math.PR #msc:60E05 #msc:60E10 #msc:68P10 #msc:68W40
paper · pdf · doi:10.48550/arxiv.math/0005235
11 pages. Refereed article, to apppear in a book edited by D. Gardy and A. Mokkadem and published in 2000 by Birkhauser
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
Using Fourier analysis, we prove that the limiting distribution of the standardized random number of comparisons used by Quicksort to sort an array of n numbers has an everywhere positive and infinitely differentiable density f, and that each derivative f(k) enjoys superpolynomial decay at plus and minus infinity. In particular, each f(k) is bounded. Our method is sufficiently computational to prove, for example, that f is bounded by 16.