Sorting today - What makes dual-pivot quicksort fast?

10^th December 2019, 13:00 Ashton Lecture Theater
Dr. Sebastian Wild
Department of Computer Science
University of Liverpool

Abstract

Quicksort is one of most well-understood algorithms - both in terms of theoretically performance guarantees and practical running time. An implementation of quicksort is part of almost every programming library. After excessive experimenting and engineering in the 1970s, the tuning efforts seemed to have converged to a stable state; but now, there is again excitement within the algorithms community, triggered by the success of a new dual-pivot quicksort used in the Java 7 runtime library.

I will introduce the new algorithm and present analytical evidence for my hypothesis why (a) dual-pivot quicksort is faster than the previously used (standard) quicksort and (b) why this basic improvement was not already found much earlier. We will then explore the potential of using even more pivots. In passing, I will demonstrate principles of algorithms science and give intuitions for my favorite mathematical tools for the analysis of algorithms.