All Publications

Average Case and Distributional Analysis of Dual-Pivot Quicksort

Jan 2015 (Written: Apr 2013)

Sebastian Wild, Markus Nebel, and Ralph Neininger:

ACM Transactions on Algorithms 11, 3, Article 22 (Jan 2015)

| read herepublisher PDFPDFDOI arXiv |

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.

ACM Author-ize Service