Perfect simulation from the quicksort limit distribution (Q1572752)

The authors consider the following problem. Let \(C_n\) denote the number of key comparisons needed to sort a list of \(n\) randomly permuted items by Quicksort. Let \(X_n ={C_n -EC_n\over n}.\) It is well known that \(X_n \to X\) as \(n\to\infty\) in distribution where \(X\) is a random variable, which distribution is the unique solution with zero mean and finite variance of the distributional fixed-point equation \(X=(D) UX^{(1)} +(1-U)X^{(2)} +c(U)\) where \(X^{(1)}\), \(X^{(2)}\), and \(U\) are independent; \(X^{(1)}\) and \(X^{(2)}\) are distributed as \(X\); \(U\) is uniform distributed in \([0, 1] \) \(e(u) = 1+2u\ln(u) +2(1-u)\ln(1-u)\) and \((D)\) denotes equality in distribution. The authors present an algorithm, which returns a perfect sample of the limit random variable \(X.\) This algorithm is based on a modified rejection method, where they use a convergent sequence of approximations for the density to decide the outcome of a rejection test.