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