QuickSort: Improved right-tail asymptotics for the limiting distribution, and large deviations

James Allen Fill, Wei-Chun Hung

Published 2019-03-19Version 1

We substantially refine asymptotic logarithmic upper bounds produced by Svante Janson (2015) on the right tail of the limiting QuickSort distribution function $F$ and by Fill and Hung (2018) on the right tails of the corresponding density $f$ and of the absolute derivatives of $f$ of each order. For example, we establish an upper bound on $\log[1 - F(x)]$ that matches conjectured asymptotics of Knessl and Szpankowski (1999) through terms of order $(\log x)^2$; the corresponding order for the Janson (2015) bound is the lead order, $x \log x$. Using the refined asymptotic bounds on $F$, we derive right-tail large deviation (LD) results for the distribution of the number of comparisons required by QuickSort that substantially sharpen the two-sided LD results of McDiarmid and Hayward (1996).