Average Case and Distributional Analysis of Dual-Pivot Quicksort
In this paper, we describe the most detailed mathematical analysis of dual-pivot Quicksort that is available in the literature:
- We compute exact average costs in the random-permutation model including Insertionsort for subarrays of size $n \le M$.
- We derive fixed-point equations for limit distributions of costs, and compute variances and covariances.
The results are discussed extensively (much more than in the conference version).
Relation to Other Papers
A shorter conference version was presented at ESA 2012.
This paper does not cover pivot sampling, since then the explicit solution of the recurrence of costs is no longer possible; we computed the leading-terms of asymptotic approximation of costs in a separate paper.
Intended Audience
algorithms experts, mathematically inclined computer scientists.
