Java 7's Dual Pivot Quicksort

Recently, a new Quicksort variant due to Yaroslavskiy 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 thesis, I try to find the reason for this unexpected success. My focus is on the precise and detailed average case analysis, aiming at the flavor of Knuth's series “The Art of Computer Programming”. In particular, I go beyond abstract measures like counting key comparisons, and try to understand the efficiency of the algorithms at different levels of abstraction. Whenever possible, precise expected values are preferred to asymptotic approximations. This rigor ensures that (a) the sorting methods discussed here are actually usable in practice and (b) that the analysis results contribute to a sound comparison of the Quicksort variants