1 Introduction
1.1 Yaroslavskiy's Algorithm
2 Preliminaries
2.1 Input Model
2.2 Basic Properties of Yaroslavskiy's Algorithm
3 Average Case Analysis
3.1 The Dual-Pivot Quicksort Recurrence
3.2 Basic Block Execution Frequencies
3.2.1 The Crossing Point Lemma
3.2.2 Frequency A
3.2.3 Frequency R
3.2.4 Frequency B
3.2.5 Frequency C1
3.2.6 Frequency S1
3.2.7 Frequency C3
3.2.8 Frequency F
3.2.9 Frequency C4
3.2.10 Frequency S3
3.3 Key Comparisons
3.4 Swaps & Write Accesses
3.5 Executed Java Bytecode Instructions
3.6 Optimal Choice for M
Remark
4 Distribution of Costs
4.1 The Contraction Method
4.2 Distributional Analysis of Yaroslavskiy's Algorithm
4.2.1 Distribution of Toll Functions
4.2.2 Distributional Recurrence
4.3 Asymptotics of Mixed Distributions
4.4 Key Comparisons
4.5 Swaps
4.6 Executed Bytecode Instructions
4.7 Covariance of Comparisons and Swaps
5 Conclusion
A Solving the Dual-Pivot Quicksort Recurrence
B Insertionsort
C Low-Level Implementations and Instruction Counts
D Details on the Distributional Analysis
D.1 Proof of Theorem 4.3
D.2 Proof of Theorem 4.4
D.3 Proof of Theorem 4.5
D.4 Proof of Theorem 4.6
D.5 Proof of Lemma 4.1
D.6 Proof of Lemma 4.2
E Experimental Validation of Asymptotics
References