Sebastian
All Publications

Average-Case Analysis of Java 7’s Dual-Pivot Quicksort

Sep 2012 (Written: Apr 2012)

Sebastian Wild and Markus Nebel:

European Symposium on Algorithms (ESA) 2012
in L. Epstein and P. Ferragina (Eds.): ESA 2012, LNCS 7501, Springer, 2012, pp 825–836

| read here | PDF | DOI | arXiv | slides |

This is the first thorough analysis of dual-pivot Quicksort and was my first conference paper ever.

It won the best paper award at ESA 2012, and is cited in the Algorithms 4th edition by Robert Sedgewick and Kevin Wayne, see Chapter 2.

Relation to Other Papers

We wrote an extended journal version of this paper together with Ralph Neininger. The full version additionally addresses

  • the analysis of Quicksort using Insertionsort for inputs of size at most $M$,
  • and the convergence of costs in distribution via the contraction method.

Intended Audience

This paper is accessible to all computer scientists.