Inaugural Lecture: Dual-Pivot Quicksort and Beyond

07 February 2018
Begin time: 
CITEC Lecture hall

In 2011 a new Quicksort variant was chosen as standard sorting method for Oracle's Java 7 runtime library. The decision for the change was based on empirical studies showing that on average, the new algorithm is faster than the formerly used classic Quicksort. Surprisingly, the improvement was achieved by using a dual pivot approach, an idea that was considered not promising by several theoretical studies in the past. In this talk we identify the reason for this unexpected success.