• 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