• Preface
  • 1 Introduction
  • 2 Foundations
    • 2.1 Common Notation & Identities
    • 2.2 Sorting: A Problem Definition
    • 2.3 Complexity of Comparison Sorting
    • 2.4 Why Analyze Algorithms?
    • 2.5 Knuthian Analysis of Algorithms
      • 2.5.1 Language Theoretic Interpretation of Knuthian Analysis
      • 2.5.2 Limitations of Knuthian Analysis
  • 3 Classic Quicksort and its Variants: Previous Work
    • 3.1 Abstract Description of Quicksort
    • 3.2 Classic Quicksort
    • 3.3 Analysis of Classic Quicksort
      • 3.3.1 Worst Case
      • 3.3.2 Average Case—Elementary Operations
      • 3.3.3 Variances
      • 3.3.4 Average Case—Processor Cycle Counts
    • 3.4 Variants of Quicksort
      • 3.4.1 Choice of the Pivot
      • 3.4.2 Implementation of the Partitioning Step
      • 3.4.3 Treatment of Short Sublists
      • 3.4.4 Multi-Pivot Quicksort
    • 3.5 Hennequin's Analysis
      • 3.5.1 Equivalence of Quicksort and Search Trees
      • 3.5.2 Combinatorial Analysis of Quicksort
      • 3.5.3 Translation to Generating Functions
      • 3.5.4 Leading Terms for alg:Hennequins-Quicksort
    • 3.6 Discussion
  • 4 Average Case Analysis of Dual-Pivot Quicksort
    • 4.1 Setting for the Analysis
      • 4.1.1 The Algorithms
      • 4.1.2 Input Model
      • 4.1.3 Elementary Operations of Sorting
    • 4.2 Recurrence Relation
      • 4.2.1 Elementary Solution
        • 4.2.1.1 Linear Partitioning Costs
      • 4.2.2 Generating Function Solution
        • 4.2.2.1 Solution to the Differential Equation
        • 4.2.2.2 Linear Partitioning Costs
    • 4.3 Partitioning Costs
      • 4.3.1 Notations
      • 4.3.2 On Positions and Values—Some More Notation
      • 4.3.3 Yaroslavskiy's Partitioning Method
        • 4.3.3.1 States After the Outer Loop
        • 4.3.3.2 c0 in alg:Dual-Pivot-Quicksort-Yaroslavskiy
        • 4.3.3.3 c1 in alg:Dual-Pivot-Quicksort-Yaroslavskiy
        • 4.3.3.4 c2 in alg:Dual-Pivot-Quicksort-Yaroslavskiy
        • 4.3.3.5 c3 in alg:Dual-Pivot-Quicksort-Yaroslavskiy
        • 4.3.3.6 c4 in alg:Dual-Pivot-Quicksort-Yaroslavskiy
        • 4.3.3.7 s0 in alg:Dual-Pivot-Quicksort-Yaroslavskiy
        • 4.3.3.8 s1 in alg:Dual-Pivot-Quicksort-Yaroslavskiy
        • 4.3.3.9 s2 in alg:Dual-Pivot-Quicksort-Yaroslavskiy
        • 4.3.3.10 s3 in alg:Dual-Pivot-Quicksort-Yaroslavskiy
        • 4.3.3.11 s4 and s5 in alg:Dual-Pivot-Quicksort-Yaroslavskiy
      • 4.3.4 Sedgewick's Partitioning Method
        • 4.3.4.1 The Crossing Point of i and j
        • 4.3.4.2 c0 in alg:Dual-Pivot-Quicksort-Sedgewick
        • 4.3.4.3 c1 in alg:Dual-Pivot-Quicksort-Sedgewick
        • 4.3.4.4 c2 in alg:Dual-Pivot-Quicksort-Sedgewick
        • 4.3.4.5 c3 in alg:Dual-Pivot-Quicksort-Sedgewick
        • 4.3.4.6 c4 in alg:Dual-Pivot-Quicksort-Sedgewick
        • 4.3.4.7 s0 in alg:Dual-Pivot-Quicksort-Sedgewick
        • 4.3.4.8 s1 in alg:Dual-Pivot-Quicksort-Sedgewick
        • 4.3.4.9 s2 in alg:Dual-Pivot-Quicksort-Sedgewick
        • 4.3.4.10 s3 in alg:Dual-Pivot-Quicksort-Sedgewick
        • 4.3.4.11 s4 and s5 in alg:Dual-Pivot-Quicksort-Sedgewick
      • 4.3.5 Re-occurring Sums
    • 4.4 Results & Discussion
      • 4.4.1 The Superiority of Yaroslavskiy's Partitioning Method
      • 4.4.2 Making Sedgewick's Dual-Pivot Quicksort Competitive
  • 5 Kciwegdes—Sedgewick Reversed
    • 5.1 Average Case Analysis
      • 5.1.1 Who Crosses Whom
      • 5.1.2 c0 in alg:Kciwegdes
      • 5.1.3 c1 in alg:Kciwegdes
      • 5.1.4 c2 in alg:Kciwegdes
      • 5.1.5 c3 in alg:Kciwegdes
      • 5.1.6 c4 in alg:Kciwegdes
    • 5.2 Results & Discussion
  • 6 Predictive Quality of the Expectation
  • 7 Counting Primitive Instructions
    • 7.1 MMIX
      • 7.1.1 Remarks for MMIX Implementations
      • 7.1.2 MMIX Implementation for alg:Classic-Quicksort
      • 7.1.3 MMIX Implementation for alg:Dual-Pivot-Quicksort-Yaroslavskiy
      • 7.1.4 MMIX Implementation for alg:Kciwegdes
    • 7.2 Java Bytecode
      • 7.2.1 Remarks for the Java Bytecode Implementations
      • 7.2.2 Bytecode Implementation for alg:Classic-Quicksort
      • 7.2.3 Bytecode Implementation for alg:Dual-Pivot-Quicksort-Yaroslavskiy
      • 7.2.4 Bytecode Implementation for alg:Kciwegdes
    • 7.3 Analyzing The Missing Frequencies
      • 7.3.1 Number of Partitions
        • 7.3.1.1 Classic Quicksort
        • 7.3.1.2 Dual-Pivot Quicksort
      • 7.3.2 Number of Recursive Calls
      • 7.3.3 X in alg:Dual-Pivot-Quicksort-Yaroslavskiy
      • 7.3.4 Y in alg:Kciwegdes
    • 7.4 Results & Discussion
      • 7.4.1 Distributing Costs to Elementary Operations
        • 7.4.1.1 Relative Runtime Contributions in alg:Classic-Quicksort
        • 7.4.1.2 Relative Runtime Contributions in alg:Dual-Pivot-Quicksort-Yaroslavskiy
        • 7.4.1.3 Relative Runtime Contributions in alg:Kciwegdes
  • 8 Runtime Study
    • 8.1 Setup for the Experiments
      • 8.1.1 Machine & Software
      • 8.1.2 Input Generation
      • 8.1.3 Runtime Measurement Methodology
    • 8.2 Runtime Comparison
    • 8.3 Discussion
  • 9 Pivot Sampling
    • 9.1 Approach of Analysis
    • 9.2 Results
      • 9.2.1 alg:Classic-Quicksort with Pivot Sampling
      • 9.2.2 alg:Dual-Pivot-Quicksort-Yaroslavskiy with Pivot Sampling
      • 9.2.3 alg:Kciwegdes with Pivot Sampling
    • 9.3 Discussion
  • 10 Conclusion
    • 10.1 Open Questions
  • Bibliography