• 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