• 1 Quicksort, What Is New?
  • 2 Quicksort and Quickselect
  • 3 Dual Pivoting
  • 4 Randomness Preservation
  • 5 Main Results
  • 6 Organization
  • 7 Preliminaries and Notation
  • 8 Analysis of Yaroslavskiy's Dual-Partitioning
  • 9 Analysis of Yaroslavskiy's Algorithm for Random Rank
    • 9.1 Exact Grand Average
    • 9.2 Limit Distribution
  • 10 Analysis of Yaroslavskiy's Algorithm for Extremal Ranks
    • 10.1 Exact Mean
    • 10.2 Limit Distribution
  • 11 Conclusion
  • References
  • A Spacings and Subproblem Sizes
  • B Proof of Convergence: Rank Smoothing
  • C Proof of Convergence: Extreme Ranks
  • D Proof of Lemma 3