1 Introduction
1.1 Cost Measures for Sorting
2 Notation and Preliminaries
3 Generalized Yaroslavskiy Quicksort
3.1 Generalized Pivot Sampling
3.2 Yaroslavskiy's Dual-Pivot Partitioning Method
3.3 Implementing Generalized Pivot Sampling
3.4 Randomness Preservation
3.5 Generalized Yaroslavskiy Quicksort
4 Results
5 Distributional Analysis
5.1 Recurrence Equations of Costs
5.2 Distribution of Partitioning Costs
5.2.1 Comparisons
5.2.2 Swaps
5.2.3 Bytecode Instructions
5.2.4 Scanned Elements
5.2.5 Distribution of Partition Sizes
5.2.6 Distribution of Pivot Values
6 Average-Case Analysis
6.1 Expected Partitioning Costs
6.2 Solution of the Recurrence
6.2.1 Rewriting the Recurrence
6.2.2 Which Case of the Master Theorem?
6.2.3 Solve by Ansatz
7 Validation
7.1 Quality of Asymptotic Approximations
7.2 Scanned Elements vs. Cache Misses
8 Discussion
8.1 Asymmetries Everywhere
8.2 Optimal Order Statistics for fixed k
8.3 Continuous ranks
8.4 Comparison with Classic Quicksort
8.4.1 Known Results for Classic Quicksort
8.4.2 Pivots from Fixed Positions
8.4.3 Pivots from Samples of Size k
9 Conclusion
Bibliography
A Index of Used Notation
B Properties of Distributions
B.1 Dirichlet Distribution and Beta Function
B.2 Multinomial Distribution
C Proof of Lemma 6.1
D Solution to the Recurrence
D.1 Finding a Shape Function
D.2 Applying the CMT