Some Results on Asymptotic Behavior of the Recalls of Random Median Quicksort

This paper investigates the asymptotic behavior of the number of recalls  Xn of the Random Median Quicksort algorithm in order to sort a list of n distinct numbers. As  n→∞, we provide the asymptotics of the expectation and variance of the recalls. Furthermore, by utilizing a refined version of the contraction method for degenerate limits, we show the limiting distribution of Xn correctly normalized is Gaussian. The theoretical results are demonstrated by a simulation study.