  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 paper, we
identify the reason for this unexpected success. Moreover, we present the first
precise average case analysis of the new algorithm showing e.g. that a random
permutation of length $n$ is sorted using $1.9n\ln n-2.46n+\mathcal{O}(\ln n)$
key comparisons and $0.6n\ln n+0.08n+\mathcal{O}(\ln n)$ swaps.
