Dual Pivot Quicksort and Beyond (long version)

I gave this talk at the research seminar of Hasso-Plattner-Institut, Potsdam about results from my dissertation (https://wild-inter.net/publications/wild-2016); it is much more comprehensive than the PhD defense talk (that has the same title).

Transcript

1. Dual-Pivot Quicksort and Beyond Sebastian Wild Forschungsseminar Hasso-Plattner-Institut 6. September 2016 It is tempting to try to develop ways to improve quicksort: a faster sorting algorithm is computer science’s “better mousetrap,” and quicksort is a venerable method that seems to invite tinkering. R. Sedgewick and K. Wayne, Algorithms 4th ed. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 1 / 22
2. Sorting History Ancient World Age of classic Quicksort Dual-Pivot Era Invention of Quicksort Dual-Pivot Quicksort in Java 1969 1975 ’78 1993 1997 1961 ’62 ’77 today 2009 ’11 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 2 / 22
3. Sorting History 1961,62 Hoare: publication, first analysis 1969 Singleton: median-of-three & Insertionsort on small subarrays 1975-78 Sedgewick: analysis of many optimizations 1993 Bentley, McIlroy: duplicate elements & “ninther” 1997 Musser: O(n log n) worst case by truncating recursion Basic algorithm settled since 1961; latest tweaks from 1990’s. Ancient World Age of classic Quicksort Dual-Pivot Era Invention of Quicksort Dual-Pivot Quicksort in Java 1969 1975 ’78 1993 1997 1961 ’62 ’77 today 2009 ’11 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 2 / 22
4. Sorting History 1961,62 Hoare: publication, first analysis 1969 Singleton: median-of-three & Insertionsort on small subarrays 1975-78 Sedgewick: analysis of many optimizations 1993 Bentley, McIlroy: duplicate elements & “ninther” 1997 Musser: O(n log n) worst case by truncating recursion Basic algorithm settled since 1961; latest tweaks from 1990’s. Ancient World Age of classic Quicksort Dual-Pivot Era Invention of Quicksort Dual-Pivot Quicksort in Java 1969 1975 ’78 1993 1997 1961 ’62 ’77 today 2009 ’11 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 2 / 22
5. Sorting History 1961,62 Hoare: publication, first analysis 1969 Singleton: median-of-three & Insertionsort on small subarrays 1975-78 Sedgewick: analysis of many optimizations 1993 Bentley, McIlroy: duplicate elements & “ninther” 1997 Musser: O(n log n) worst case by truncating recursion Basic algorithm settled since 1961; latest tweaks from 1990’s. Since then: Almost identical in all programming libraries! Ancient World Age of classic Quicksort Dual-Pivot Era Invention of Quicksort Dual-Pivot Quicksort in Java 1969 1975 ’78 1993 1997 1961 ’62 ’77 today 2009 ’11 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 2 / 22
6. Sorting History 2008 – 2009 Vladimir Yaroslavskiy (developer at Sun) experiments with Quicksort with two pivots 2009 – 2011 optimizations by Joshua Bloch, Jon Bentley and others 11 Sep 2009 announcement on Java core library mailing list 29 Oct 2009 inclusion in development version of OpenJDK 28 July 2011 public release of Java 7 (same in Java 8) with Yaroslavskiy-Bentley-Block (YBB) Quicksort Ancient World Age of classic Quicksort Dual-Pivot Era Invention of Quicksort Dual-Pivot Quicksort in Java 1969 1975 ’78 1993 1997 1961 ’62 ’77 today 2009 ’11 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 2 / 22
7. Running Time Experiments Why change a well-tested implementation? 0 0.5 1 1.5 2 ·106 7 8 9 n time 10−6 · n ln n Normalized Java runtimes (in ms). Average of 1000 random permutations per size. YBB Quicksort significantly faster! ...just new engineering tricks? Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 3 / 22
8. Running Time Experiments Why change a well-tested implementation? 0 0.5 1 1.5 2 ·106 7 8 9 n time 10−6 · n ln n Java 6 Library (121ms to sort 1M ints) Normalized Java runtimes (in ms). Average of 1000 random permutations per size. YBB Quicksort significantly faster! ...just new engineering tricks? Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 3 / 22
9. Running Time Experiments Why change a well-tested implementation? 0 0.5 1 1.5 2 ·106 7 8 9 n time 10−6 · n ln n Java 6 Library Java 7 Library (121ms to sort 1M ints) (93ms to sort 1M ints) Normalized Java runtimes (in ms). Average of 1000 random permutations per size. YBB Quicksort significantly faster! ...just new engineering tricks? Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 3 / 22
10. Running Time Experiments Why change a well-tested implementation? 0 0.5 1 1.5 2 ·106 7 8 9 n time 10−6 · n ln n Java 6 Library Java 7 Library (121ms to sort 1M ints) (93ms to sort 1M ints) Normalized Java runtimes (in ms). Average of 1000 random permutations per size. YBB Quicksort significantly faster! ...just new engineering tricks? Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 3 / 22
11. Running Time Experiments Why change a well-tested implementation? 0 0.5 1 1.5 2 ·106 7 8 9 n time 10−6 · n ln n Java 6 Library Java 7 Library (121ms to sort 1M ints) (93ms to sort 1M ints) Normalized Java runtimes (in ms). Average of 1000 random permutations per size. YBB Quicksort significantly faster! ...just new engineering tricks? • exploit (partially) sorted inputs • handle equal items efficiently • Insertionsort for small subproblems (actually pair insertion) • choose good pivots • use sentinel elements • low-level optimizations Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 3 / 22
12. Running Time Experiments Why change a well-tested implementation? 0 0.5 1 1.5 2 ·106 7 8 9 n time 10−6 · n ln n Java 6 Library Java 7 Library Classic Quicksort YBB Quicksort (121ms to sort 1M ints) (93ms to sort 1M ints) Normalized Java runtimes (in ms). Average of 1000 random permutations per size. YBB Quicksort significantly faster! ...just new engineering tricks? • exploit (partially) sorted inputs • handle equal items efficiently • Insertionsort for small subproblems (actually pair insertion) • choose good pivots • use sentinel elements • low-level optimizations No: remains true for basic variants of algorithms: vs. ! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 3 / 22
13. Dual-Pivot Quicksort: Conceptual View Single-Pivot Quicksort 1 Choose pivots P. 2 For each element x, determine its class small for x < P large for P < x by comparing x to P. 3 Arrange elements according to classes: P 4 Sort subarrays recursively. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 4 / 22
14. Dual-Pivot Quicksort: Conceptual View Single-Pivot Quicksort 1 Choose pivots P. 2 For each element x, determine its class small for x < P large for P < x by comparing x to P. 3 Arrange elements according to classes: P 4 Sort subarrays recursively. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 4 / 22
15. Dual-Pivot Quicksort: Conceptual View Single-Pivot Quicksort 1 Choose pivots P. 2 For each element x, determine its class small for x < P large for P < x by comparing x to P. 3 Arrange elements according to classes: P 4 Sort subarrays recursively. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 4 / 22
16. Dual-Pivot Quicksort: Conceptual View Single-Pivot Quicksort 1 Choose pivots P. 2 For each element x, determine its class small for x < P assuming distinct elements in this talk large for P < x by comparing x to P. 3 Arrange elements according to classes: P 4 Sort subarrays recursively. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 4 / 22
17. Dual-Pivot Quicksort: Conceptual View Single-Pivot Quicksort 1 Choose pivots P. 2 For each element x, determine its class small for x < P assuming distinct elements in this talk large for P < x by comparing x to P. 3 Arrange elements according to classes: P 4 Sort subarrays recursively. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 4 / 22
18. Dual-Pivot Quicksort: Conceptual View Single-Pivot Quicksort 1 Choose pivots P. 2 For each element x, determine its class small for x < P assuming distinct elements in this talk large for P < x by comparing x to P. 3 Arrange elements according to classes: P 4 Sort subarrays recursively. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 4 / 22
19. Dual-Pivot Quicksort: Conceptual View Single-Pivot Quicksort 1 Choose pivots P. 2 For each element x, determine its class small for x < P assuming distinct elements in this talk large for P < x by comparing x to P. 3 Arrange elements according to classes: P 4 Sort subarrays recursively. Dual-Pivot Quicksort 1 Choose two pivots P Q 2 For each element x, determine its class small for x < P medium for P < x < Q large for Q < x by comparing x to pivots P and Q 3 Arrange elements according to classes: P Q 4 Sort subarrays recursively. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 4 / 22
20. Dual-Pivot Quicksort: Conceptual View Single-Pivot Quicksort 1 Choose pivots P. 2 For each element x, determine its class small for x < P assuming distinct elements in this talk large for P < x by comparing x to P. 3 Arrange elements according to classes: P 4 Sort subarrays recursively. Dual-Pivot Quicksort 1 Choose two pivots P Q 2 For each element x, determine its class small for x < P medium for P < x < Q large for Q < x by comparing x to pivots P and Q 3 Arrange elements according to classes: P Q 4 Sort subarrays recursively. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 4 / 22
21. Dual-Pivot Quicksort: Conceptual View Single-Pivot Quicksort 1 Choose pivots P. 2 For each element x, determine its class small for x < P assuming distinct elements in this talk large for P < x by comparing x to P. 3 Arrange elements according to classes: P 4 Sort subarrays recursively. Dual-Pivot Quicksort 1 Choose two pivots P Q 2 For each element x, determine its class small for x < P medium for P < x < Q large for Q < x by comparing x to pivots P and Q 3 Arrange elements according to classes: P Q 4 Sort subarrays recursively. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 4 / 22
22. Dual-Pivot Quicksort: Conceptual View Single-Pivot Quicksort 1 Choose pivots P. 2 For each element x, determine its class small for x < P assuming distinct elements in this talk large for P < x by comparing x to P. 3 Arrange elements according to classes: P 4 Sort subarrays recursively. Dual-Pivot Quicksort 1 Choose two pivots P Q 2 For each element x, determine its class small for x < P medium for P < x < Q large for Q < x by comparing x to pivots P and Q 3 Ar Dijkstra’s Dutch National Flag Problem range elements according to classes: P Q 4 Sort subarrays recursively. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 4 / 22
23. Dual-Pivot Quicksort: Conceptual View Single-Pivot Quicksort 1 Choose pivots P. 2 For each element x, determine its class small for x < P assuming distinct elements in this talk large for P < x by comparing x to P. 3 Arrange elements according to classes: P 4 Sort subarrays recursively. Dual-Pivot Quicksort 1 Choose two pivots P Q 2 For each element x, determine its class small for x < P medium for P < x < Q large for Q < x by comparing x to pivots P and Q 3 Ar Dijkstra’s Dutch National Flag Problem range elements according to classes: P Q 4 Sort subarrays recursively. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 4 / 22
24. Dual-Pivot Quicksort: Conceptual View Single-Pivot Quicksort 1 Choose pivots P. 2 For each element x, determine its class small for x < P assuming distinct elements in this talk large for P < x by comparing x to P. 3 Arrange elements according to classes: P 4 Sort subarrays recursively. Dual-Pivot Quicksort 1 Choose two pivots P Q 2 For each element x, determine its class small for x < P medium for P < x < Q large for Q < x by comparing x to pivots P and Q 3 Ar Dijkstra’s Dutch National Flag Problem range elements according to classes: P Q 4 Sort subarrays recursively. How to do 3 efficiently and in place? YBB Partitioning Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 4 / 22
25. Dual-Pivot Quicksort: Conceptual View Single-Pivot Quicksort 1 Choose pivots P. 2 For each element x, determine its class small for x < P assuming distinct elements in this talk large for P < x by comparing x to P. 3 Arrange elements according to classes: P 4 Sort subarrays recursively. Dual-Pivot Quicksort 1 Choose two pivots P Q 2 For each element x, determine its class small for x < P medium for P < x < Q large for Q < x by comparing x to pivots P and Q 3 Ar Dijkstra’s Dutch National Flag Problem range elements according to classes: P Q 4 Sort subarrays recursively. How to do 3 efficiently and in place? YBB Partitioning Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 4 / 22
26. Basic Algorithms CLASSICQUICKSORT(A, left, right) 1 if right left then return 2 P = A[right] 3 k = left − 1; g = right 4 while true 5 do k = k + 1 while A[k] < P end while 6 do g = g − 1 while A[g] > P end while 7 if k g then break while end if 8 Swap A[k] and A[g] 9 end while 10 Swap A[k] and A[right] 11 CLASSICQUICKSORT(A, left , k − 1) 12 CLASSICQUICKSORT(A, k + 1, right ) YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 5 / 22
27. Basic Algorithms CLASSICQUICKSORT(A, left, right) 1 if right left then return 2 P = A[right] 3 k = left − 1; g = right 4 while true 5 do k = k + 1 while A[k] < P end while 6 do g = g − 1 while A[g] > P end while 7 if k g then break while end if 8 Swap A[k] and A[g] 9 end while 10 Swap A[k] and A[right] 11 CLASSICQUICKSORT(A, left , k − 1) 12 CLASSICQUICKSORT(A, k + 1, right ) YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 5 / 22
28. Basic Algorithms CLASSICQUICKSORT(A, left, right) 1 if right left then return 2 P = A[right] 3 k = left − 1; g = right 4 while true 5 do k = k + 1 while A[k] < P end while 6 do g = g − 1 while A[g] > P end while 7 if k g then break while end if 8 Swap A[k] and A[g] 9 end while 10 Swap A[k] and A[right] 11 CLASSICQUICKSORT(A, left , k − 1) 12 CLASSICQUICKSORT(A, k + 1, right ) Classic Quicksort crossing-pointer scheme symmetric YBB Quicksort ...looks messy YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 5 / 22
29. Basic Algorithms CLASSICQUICKSORT(A, left, right) 1 if right left then return 2 P = A[right] 3 k = left − 1; g = right 4 while true 5 do k = k + 1 while A[k] < P end while 6 do g = g − 1 while A[g] > P end while 7 if k g then break while end if 8 Swap A[k] and A[g] 9 end while 10 Swap A[k] and A[right] 11 CLASSICQUICKSORT(A, left , k − 1) 12 CLASSICQUICKSORT(A, k + 1, right ) Classic Quicksort crossing-pointer scheme symmetric YBB Quicksort ...looks messy YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 5 / 22
30. Basic Algorithms CLASSICQUICKSORT(A, left, right) 1 if right left then return 2 P = A[right] 3 k = left − 1; g = right 4 while true 5 do k = k + 1 while A[k] < P end while 6 do g = g − 1 while A[g] > P end while 7 if k g then break while end if 8 Swap A[k] and A[g] 9 end while 10 Swap A[k] and A[right] 11 CLASSICQUICKSORT(A, left , k − 1) 12 CLASSICQUICKSORT(A, k + 1, right ) Classic Quicksort crossing-pointer scheme symmetric YBB Quicksort ...looks messy YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 5 / 22
31. Basic Algorithms CLASSICQUICKSORT(A, left, right) 1 if right left then return 2 P = A[right] 3 k = left − 1; g = right 4 while true 5 do k = k + 1 while A[k] < P end while 6 do g = g − 1 while A[g] > P end while 7 if k g then break while end if 8 Swap A[k] and A[g] 9 end while 10 Swap A[k] and A[right] 11 CLASSICQUICKSORT(A, left , k − 1) 12 CLASSICQUICKSORT(A, k + 1, right ) Classic Quicksort crossing-pointer scheme symmetric YBB Quicksort ...looks messy YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 5 / 22
32. Basic Algorithms CLASSICQUICKSORT(A, left, right) 1 if right left then return 2 P = A[right] 3 k = left − 1; g = right 4 while true 5 do k = k + 1 while A[k] < P end while 6 do g = g − 1 while A[g] > P end while 7 if k g then break while end if 8 Swap A[k] and A[g] 9 end while 10 Swap A[k] and A[right] 11 CLASSICQUICKSORT(A, left , k − 1) 12 CLASSICQUICKSORT(A, k + 1, right ) Classic Quicksort crossing-pointer scheme symmetric YBB Quicksort ...looks messy YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 5 / 22
33. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 5 1 7 4 2 8 6 g k P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
34. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 5 1 7 4 2 8 6 g k P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
35. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 5 1 7 4 2 8 6 g k P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
36. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 5 1 7 4 2 8 6 g k P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
37. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 5 1 7 4 2 8 6 g k P≤◦≤Q P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
38. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 5 1 7 4 2 8 6 g k P≤◦≤Q P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
39. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 1 5 7 4 2 8 6 g k P≤◦≤Q P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
40. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 1 5 7 4 2 8 6 g k < P P≤◦≤Q P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
41. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 1 5 7 4 2 8 6 g k < P P≤◦≤Q P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
42. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 1 5 7 4 2 8 6 g k < P P≤◦≤Q P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
43. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 1 5 7 4 2 8 6 g k < P P≤◦≤Q P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
44. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 1 5 7 4 2 8 6 g k < P P≤◦≤Q P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
45. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 1 5 7 4 2 8 6 g k < P P≤◦≤Q ≥ Q P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
46. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 1 5 7 4 2 8 6 g k < P P≤◦≤Q ≥ Q P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
47. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 1 5 7 4 2 8 6 g k < P P≤◦≤Q ≥ Q P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
48. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 1 2 5 4 7 8 6 g k < P P≤◦≤Q ≥ Q P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
49. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 1 2 5 4 7 8 6 g k < P P≤◦≤Q ≥ Q P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
50. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 1 2 5 4 7 8 6 g k < P P≤◦≤Q ≥ Q P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
51. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 1 2 5 4 7 8 6 g k < P P≤◦≤Q ≥ Q P Q Invariant: YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
52. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 3 1 2 5 4 7 8 6 YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
53. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 2 1 3 5 4 6 8 7 YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
54. YBB Partitioning Example < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     P Q 1 2 3 4 5 6 7 8 YBBQUICKSORT(A, left, right) 1 if right left then return 2 P = A[left]; Q = A[right] 3 if P > Q then Swap P and Q end if 4 = left + 1; g = right − 1; k = 5 while k g 6 if A[k] < P 7 Swap A[k] and A[ ] ; = + 1 8 else if A[k] Q 9 while A[g] > Q and k < g 10 g = g − 1 11 end while 12 Swap A[k] and A[g] ; g = g − 1 13 if A[k] < P 14 Swap A[k] and A[ ] ; = + 1 15 end if 16 end if 17 k = k + 1 18 end while 19 = − 1; g = g + 1 20 Swap A[left] and A[ ] ; Swap A[right] and A[g] 21 YBBQUICKSORT(A, left , − 1) 22 YBBQUICKSORT(A, + 1, g − 1) 23 YBBQUICKSORT(A, g + 1, right ) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 6 / 22
55. Comparisons How many comparisons on average? < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     Consider first partitioning step. How many #cmps per element? Well, either 2 or 1 . How many on average? Analysis Sketch: Have to compare with one pivot first, say P. 1 cmp for small elements, 2 cmps for medium and large . (Similar if Q used first.) On average, ∼ 1 3 n elements each kind. on average 2 · 2 3 + 1 · 1 3 = 5 3 cmps per element Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 7 / 22
56. Comparisons How many comparisons on average? < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     Consider first partitioning step. How many #cmps per element? Well, either 2 or 1 . How many on average? Analysis Sketch: Have to compare with one pivot first, say P. 1 cmp for small elements, 2 cmps for medium and large . (Similar if Q used first.) On average, ∼ 1 3 n elements each kind. on average 2 · 2 3 + 1 · 1 3 = 5 3 cmps per element Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 7 / 22
57. Comparisons How many comparisons on average? < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     Consider first partitioning step. How many #cmps per element? Well, either 2 or 1 . How many on average? Analysis Sketch: Have to compare with one pivot first, say P. 1 cmp for small elements, 2 cmps for medium and large . (Similar if Q used first.) On average, ∼ 1 3 n elements each kind. on average 2 · 2 3 + 1 · 1 3 = 5 3 cmps per element Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 7 / 22
58. Comparisons How many comparisons on average? < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     Consider first partitioning step. How many #cmps per element? Well, either 2 or 1. How many on average? Analysis Sketch: Have to compare with one pivot first, say P. 1 cmp for small elements, 2 cmps for medium and large . (Similar if Q used first.) On average, ∼ 1 3 n elements each kind. on average 2 · 2 3 + 1 · 1 3 = 5 3 cmps per element Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 7 / 22
59. Comparisons How many comparisons on average? < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     Consider first partitioning step. How many #cmps per element? Well, either 2 or 1 . How many on average? Analysis Sketch: Have to compare with one pivot first, say P. 1 cmp for small elements, 2 cmps for medium and large . (Similar if Q used first.) On average, ∼ 1 3 n elements each kind. on average 2 · 2 3 + 1 · 1 3 = 5 3 cmps per element Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 7 / 22
60. Comparisons How many comparisons on average? < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     Consider first partitioning step. How many #cmps per element? Well, either 2 or 1 . How many on average? Analysis Sketch: Have to compare with one pivot first, say P. 1 cmp for small elements, 2 cmps for medium and large . (Similar if Q used first.) On average, ∼ 1 3 n elements each kind. on average 2 · 2 3 + 1 · 1 3 = 5 3 cmps per element Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 7 / 22
61. Comparisons How many comparisons on average? < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     Consider first partitioning step. How many #cmps per element? Well, either 2 or 1 . How many on average? Analysis Sketch: Have to compare with one pivot first, say P. 1 cmp for small elements, 2 cmps for medium and large . (Similar if Q used first.) On average, ∼ 1 3 n elements each kind. on average 2 · 2 3 + 1 · 1 3 = 5 3 cmps per element Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 7 / 22
62. Comparisons How many comparisons on average? < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     Consider first partitioning step. How many #cmps per element? Well, either 2 or 1 . How many on average? Analysis Sketch: Have to compare with one pivot first, say P. 1 cmp for small elements, 2 cmps for medium and large . (Similar if Q used first.) On average, ∼ 1 3 n elements each kind. on average 2 · 2 3 + 1 · 1 3 = 5 3 cmps per element Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 7 / 22
63. Comparisons How many comparisons on average? < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     Consider first partitioning step. How many #cmps per element? Well, either 2 or 1 . How many on average? Analysis Sketch: Have to compare with one pivot first, say P. 1 cmp for small elements, 2 cmps for medium and large . (Similar if Q used first.) On average, ∼ 1 3 n elements each kind. on average 2 · 2 3 + 1 · 1 3 = 5 3 cmps per element Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 7 / 22
64. Comparisons How many comparisons on average? < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     Consider first partitioning step. How many #cmps per element? Well, either 2 or 1 . How many on average? Analysis Sketch: Have to compare with one pivot first, say P. 1 cmp for small elements, 2 cmps for medium and large . (Similar if Q used first.) On average, ∼ 1 3 n elements each kind. on average 2 · 2 3 + 1 · 1 3 = 5 3 cmps per element Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 7 / 22
65. Comparisons How many comparisons on average? < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     Consider first partitioning step. How many #cmps per element? Well, either 2 or 1 . How many on average? Analysis Sketch: Have to compare with one pivot first, say P. 1 cmp for small elements, 2 cmps for medium and large . (Similar if Q used first.) On average, ∼ 1 3 n elements each kind. on average 2 · 2 3 + 1 · 1 3 = 5 3 cmps per element Sounds plausible? Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 7 / 22
66. Comparisons How many comparisons on average? < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     Consider first partitioning step. How many #cmps per element? Well, either 2 or 1 . How many on average? Analysis Sketch: Have to compare with one pivot first, say P. 1 cmp for small elements, 2 cmps for medium and large . (Similar if Q used first.) On average, ∼ 1 3 n elements each kind. on average 2 · 2 3 + 1 · 1 3 = 5 3 cmps per element Sounds plausible? ...but it’s wrong! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 7 / 22
67. Comparisons How many comparisons on average? < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     Consider first partitioning step. How many #cmps per element? Well, either 2 or 1 . How many on average? Analysis Sketch: Have to compare with one pivot first, say P. 1 cmp for small elements, 2 cmps for medium and large . (Similar if Q used first.) On average, ∼ 1 3 n elements each kind. on average 2 · 2 3 + 1 · 1 3 = 5 3 cmps per element Sounds plausible? ...but it’s wrong! Problem: There are correlations. many small elements k’s range big many large elements g’s range big > 1 3 cheap elements on average. How many? ...stay tuned. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 7 / 22
68. Comparisons How many comparisons on average? < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     Consider first partitioning step. How many #cmps per element? Well, either 2 or 1 . How many on average? Analysis Sketch: Have to compare with one pivot first, say P. 1 cmp for small elements, 2 cmps for medium and large . (Similar if Q used first.) On average, ∼ 1 3 n elements each kind. on average 2 · 2 3 + 1 · 1 3 = 5 3 cmps per element Sounds plausible? ...but it’s wrong! Problem: There are correlations. many small elements k’s range big many large elements g’s range big > 1 3 cheap elements on average. How many? ...stay tuned. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 7 / 22
69. Comparisons How many comparisons on average? < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     Consider first partitioning step. How many #cmps per element? Well, either 2 or 1 . How many on average? Analysis Sketch: Have to compare with one pivot first, say P. 1 cmp for small elements, 2 cmps for medium and large . (Similar if Q used first.) On average, ∼ 1 3 n elements each kind. on average 2 · 2 3 + 1 · 1 3 = 5 3 cmps per element Sounds plausible? ...but it’s wrong! Problem: There are correlations. many small elements k’s range big many large elements g’s range big > 1 3 cheap elements on average. How many? ...stay tuned. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 7 / 22
70. Comparisons How many comparisons on average? < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     Consider first partitioning step. How many #cmps per element? Well, either 2 or 1 . How many on average? Analysis Sketch: Have to compare with one pivot first, say P. 1 cmp for small elements, 2 cmps for medium and large . (Similar if Q used first.) On average, ∼ 1 3 n elements each kind. on average 2 · 2 3 + 1 · 1 3 = 5 3 cmps per element Sounds plausible? ...but it’s wrong! Problem: There are correlations. many small elements k’s range big many large elements g’s range big > 1 3 cheap elements on average. How many? ...stay tuned. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 7 / 22
71. Comparisons How many comparisons on average? < P ? swap < Q ? skip swap g     > Q ? < P ? skip swap swap k     Consider first partitioning step. How many #cmps per element? Well, either 2 or 1 . How many on average? Analysis Sketch: Have to compare with one pivot first, say P. 1 cmp for small elements, 2 cmps for medium and large . (Similar if Q used first.) On average, ∼ 1 3 n elements each kind. on average 2 · 2 3 + 1 · 1 3 = 5 3 cmps per element Sounds plausible? ...but it’s wrong! Problem: There are correlations. many small elements k’s range big many large elements g’s range big > 1 3 cheap elements on average. How many? ...stay tuned. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 7 / 22
72. Random Model n i.i.d. elements chosen uniformly in (0, 1) 0 1 U1 U2 U3 U4 U5 U6 U7 U8 pairwise distinct almost surely relative ranking is a random permutation equivalent to classic model For dual-pivot Quicksort with fixed pivots P Q Pr U < P = D1 Pr P < U < Q = D2 Pr U > Q = D3 0 1 P Q Known distribution: D = (D1, D2, D3) D = Dirichlet(1, 1, 1). (D1, D2) uniform in 2D simplex x, y ∈ (0, 1) : x + y < 1 0 0.5 1 0 0.5 1 0 0.5 1 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 8 / 22
73. Random Model n i.i.d. elements chosen uniformly in (0, 1) 0 1 U1 U2 U3 U4 U5 U6 U7 U8 pairwise distinct almost surely relative ranking is a random permutation equivalent to classic model For dual-pivot Quicksort with fixed pivots P Q Pr U < P = D1 Pr P < U < Q = D2 Pr U > Q = D3 0 1 P Q Known distribution: D = (D1, D2, D3) D = Dirichlet(1, 1, 1). (D1, D2) uniform in 2D simplex x, y ∈ (0, 1) : x + y < 1 0 0.5 1 0 0.5 1 0 0.5 1 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 8 / 22
74. Random Model n i.i.d. elements chosen uniformly in (0, 1) 0 1 U1 U2 U3 U4 U5 U6 U7 U8 pairwise distinct almost surely relative ranking is a random permutation equivalent to classic model For dual-pivot Quicksort with fixed pivots P Q Pr U < P = D1 Pr P < U < Q = D2 Pr U > Q = D3 0 1 P Q Known distribution: D = (D1, D2, D3) D = Dirichlet(1, 1, 1). (D1, D2) uniform in 2D simplex x, y ∈ (0, 1) : x + y < 1 0 0.5 1 0 0.5 1 0 0.5 1 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 8 / 22
75. Random Model n i.i.d. elements chosen uniformly in (0, 1) 0 1 U1 U2 U3 U4 U5 U6 U7 U8 pairwise distinct almost surely relative ranking is a random permutation equivalent to classic model For dual-pivot Quicksort with fixed pivots P Q Pr U < P = D1 Pr P < U < Q = D2 Pr U > Q = D3 0 1 P Q Known distribution: D = (D1, D2, D3) D = Dirichlet(1, 1, 1). (D1, D2) uniform in 2D simplex x, y ∈ (0, 1) : x + y < 1 0 0.5 1 0 0.5 1 0 0.5 1 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 8 / 22
76. Random Model n i.i.d. elements chosen uniformly in (0, 1) 0 1 U1 U2 U3 U4 U5 U6 U7 U8 pairwise distinct almost surely relative ranking is a random permutation equivalent to classic model For dual-pivot Quicksort with fixed pivots P Q Pr U < P = D1 Pr P < U < Q = D2 Pr U > Q = D3 0 1 P Q Known distribution: D = (D1, D2, D3) D = Dirichlet(1, 1, 1). (D1, D2) uniform in 2D simplex x, y ∈ (0, 1) : x + y < 1 0 0.5 1 0 0.5 1 0 0.5 1 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 8 / 22
77. Random Model n i.i.d. elements chosen uniformly in (0, 1) 0 1 U1 U2 U3 U4 U5 U6 U7 U8 pairwise distinct almost surely relative ranking is a random permutation equivalent to classic model For dual-pivot Quicksort with fixed pivots P Q Pr U < P = D1 Pr P < U < Q = D2 Pr U > Q = D3 0 1 P Q Known distribution: D = (D1, D2, D3) D = Dirichlet(1, 1, 1). (D1, D2) uniform in 2D simplex x, y ∈ (0, 1) : x + y < 1 0 0.5 1 0 0.5 1 0 0.5 1 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 8 / 22
78. Random Model n i.i.d. elements chosen uniformly in (0, 1) 0 1 U1 U2 U3 U4 U5 U6 U7 U8 pairwise distinct almost surely relative ranking is a random permutation equivalent to classic model For dual-pivot Quicksort with fixed pivots P Q Pr U < P = D1 Pr P < U < Q = D2 Pr U > Q = D3 0 1 P Q D1 D2 D3 Known distribution: D = (D1, D2, D3) D = Dirichlet(1, 1, 1). (D1, D2) uniform in 2D simplex x, y ∈ (0, 1) : x + y < 1 0 0.5 1 0 0.5 1 0 0.5 1 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 8 / 22
79. Random Model n i.i.d. elements chosen uniformly in (0, 1) 0 1 U1 U2 U3 U4 U5 U6 U7 U8 pairwise distinct almost surely relative ranking is a random permutation equivalent to classic model For dual-pivot Quicksort with fixed pivots P Q Pr U < P = D1 Pr P < U < Q = D2 Pr U > Q = D3 0 1 P Q D1 D2 D3 Known distribution: D = (D1, D2, D3) D = Dirichlet(1, 1, 1). (D1, D2) uniform in 2D simplex x, y ∈ (0, 1) : x + y < 1 0 0.5 1 0 0.5 1 0 0.5 1 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 8 / 22
80. Random Model n i.i.d. elements chosen uniformly in (0, 1) 0 1 U1 U2 U3 U4 U5 U6 U7 U8 pairwise distinct almost surely relative ranking is a random permutation equivalent to classic model For dual-pivot Quicksort with fixed pivots P Q Pr U < P = D1 Pr P < U < Q = D2 Pr U > Q = D3 0 1 P Q D1 D2 D3 Known distribution: D itself a (random) prob. distribution = (D1, D2, D3) D = Dirichlet(1, 1, 1). (D1, D2) uniform in 2D simplex x, y ∈ (0, 1) : x + y < 1 0 0.5 1 0 0.5 1 0 0.5 1 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 8 / 22
81. Random Model n i.i.d. elements chosen uniformly in (0, 1) 0 1 U1 U2 U3 U4 U5 U6 U7 U8 pairwise distinct almost surely relative ranking is a random permutation equivalent to classic model For dual-pivot Quicksort with fixed pivots P Q Pr U < P = D1 Pr P < U < Q = D2 Pr U > Q = D3 0 1 P Q D1 D2 D3 Known distribution: D itself a (random) prob. distribution = (D1, D2, D3) D = Dirichlet(1, 1, 1). (D1, D2) uniform in 2D simplex x, y ∈ (0, 1) : x + y < 1 0 0.5 1 0 0.5 1 0 0.5 1 These probabilities hold for all elements U, independent of all other elements! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 8 / 22
82. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 E[ l @ G ] ∼ E D3 · D3 · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
83. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 E[ l @ G ] ∼ E D3 · D3 · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
84. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 E[ l @ G ] ∼ E D3 · D3 · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
85. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G ] ∼ E D3 · D3 · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
86. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n 2 cmps/element − E[s@ K ] −1 for cheap elements − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G ] ∼ E D3 · D3 · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
87. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n 2 cmps/element − E[s@ K ] −1 for cheap elements − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G ] ∼ E D3 · D3 · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
88. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult multivariate binomial (n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G ] ∼ E D3 · D3 · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
89. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult multivariate binomial (n − 2, D) I = Dn ± O(n1/2+ε) whp Chernoff bound 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G ] ∼ E D3 · D3 · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
90. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult multivariate binomial (n − 2, D) I = Dn ± O(n1/2+ε) whp Chernoff bound 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G ] ∼ E D3 · D3 · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
91. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G ] ∼ E D3 fraction of large elements · D3 · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
92. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G ] ∼ E D3 fraction of large elements · D3 fraction of elements in K · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
93. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G To be precise, we have conditional on I: l @ G D = HypG(n − 2; I3 , I3 ) E[ l @ G | I] = I3 · I3 n − 2 1 3 4 6 7 2 8 5 Draw positions of large elements 1 2 3 4 5 6 7 8 ] ∼ E D3 fraction of large elements · D3 fraction of elements in K · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
94. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G To be precise, we have conditional on I: l @ G D = HypG(n − 2; I3 , I3 ) E[ l @ G | I] = I3 · I3 n − 2 1 3 4 6 7 2 8 5 Draw positions of large elements 1 2 3 4 5 6 7 8 ] ∼ E D3 fraction of large elements · D3 fraction of elements in K · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
95. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G To be precise, we have conditional on I: l @ G D = HypG(n − 2; I3 , I3 ) E[ l @ G | I] = I3 · I3 n − 2 1 3 4 6 7 2 8 5 Draw positions of large elements 1 2 3 4 5 6 7 8 ] ∼ E D3 fraction of large elements · D3 fraction of elements in K · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
96. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G To be precise, we have conditional on I: l @ G D = HypG(n − 2; I3 , I3 ) E[ l @ G | I] = I3 · I3 n − 2 1 3 4 6 7 2 8 5 Draw positions of large elements 1 2 3 4 5 6 7 8 ] ∼ E D3 fraction of large elements · D3 fraction of elements in K · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
97. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G To be precise, we have conditional on I: l @ G D = HypG(n − 2; I3 , I3 ) E[ l @ G | I] = I3 · I3 n − 2 1 3 4 6 7 2 8 5 Draw positions of large elements 1 2 3 4 5 6 7 8 l @ G = 1 ] ∼ E D3 fraction of large elements · D3 fraction of elements in K · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
98. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G To be precise, we have conditional on I: l @ G D = HypG(n − 2; I3 , I3 ) E[ l @ G | I] = I3 · I3 n − 2 1 3 4 6 7 2 8 5 Draw positions of large elements 1 2 3 4 5 6 7 8 l @ G = 1 ] ∼ E D3 fraction of large elements · D3 fraction of elements in K · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
99. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G ] ∼ E D3 fraction of large elements · D3 fraction of elements in K · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
100. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G ] ∼ E D3 fraction of large elements · D3 fraction of elements in K = 1 6 > 1 3 · 1 3 · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
101. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G ] ∼ E D3 fraction of large elements · D3 fraction of elements in K = 1 6 > 1 3 · 1 3 · n, E[s@ K ] ∼ E D1 · (D1 + D2) · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
102. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G ] ∼ E D3 fraction of large elements · D3 fraction of elements in K = 1 6 > 1 3 · 1 3 · n, E[s@ K ] ∼ E D1 · (D1 + D2) = 1 4 > 1 3 · 2 3 · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
103. Comparisons in YBB Partitioning t(n): E[#cmps] in first partitioning step I1 : number of small elements; I2 , I3 similar K : #elements scanned by k; K ∼ I1 + I2 s@ K : # small elements in k ’s range; l @ G similar < P Q P ◦ Q k’s range K G I1 I2 I3 t(n) ∼ 2n − E[s@ K ] − E[ l @ G ] ∼ 19 12 n ...what is E[s@ K ]? Consider fixed D, I = (I1, I2, I3) D = Mult(n − 2, D) I = Dn ± O(n1/2+ε) whp 0 1 P Q D1 D2 D3 I1 I2 I3 E[ l @ G ] ∼ E D3 fraction of large elements · D3 fraction of elements in K = 1 6 > 1 3 · 1 3 · n, E[s@ K ] ∼ E D1 · (D1 + D2) = 1 4 > 1 3 · 2 3 · n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 9 / 22
104. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) 3 r=1 E[Dr] + αn 3 r=1 E[Dr ln(Dr)] indeed (by induction): c(n) = 19 10 n ln n ± O(n). Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
105. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) ∼ 19 12 n + E c(I1) + E c(I2) + E c(I3) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) 3 r=1 E[Dr] + αn 3 r=1 E[Dr ln(Dr)] indeed (by induction): c(n) = 19 10 n ln n ± O(n). Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
106. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) ∼ 19 12 n + E c(I1 concentrated around D1 n ) + E c(I2) + E c(I3) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) 3 r=1 E[Dr] + αn 3 r=1 E[Dr ln(Dr)] indeed (by induction): c(n) = 19 10 n ln n ± O(n). Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
107. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) ∼ 19 12 n + E c(I1 concentrated around D1 n ) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) 3 r=1 E[Dr] + αn 3 r=1 E[Dr ln(Dr)] indeed (by induction): c(n) = 19 10 n ln n ± O(n). Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
108. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) 3 r=1 E[Dr] + αn 3 r=1 E[Dr ln(Dr)] indeed (by induction): c(n) = 19 10 n ln n ± O(n). Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
109. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) logeαn ln(n) = 19 12 n + αn ln(n) 3 r=1 E[Dr] + αn 3 r=1 E[Dr ln(Dr)] indeed (by induction): c(n) = 19 10 n ln n ± O(n). Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
110. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) 3 r=1 E[Dr] + αn 3 r=1 E[Dr ln(Dr)] indeed (by induction): c(n) = 19 10 n ln n ± O(n). Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
111. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) =1 3 r=1 E[Dr] + αn 3 r=1 E[Dr ln(Dr)] indeed (by induction): c(n) = 19 10 n ln n ± O(n). Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
112. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) =1 3 r=1 E[Dr] + αn 3 r=1 E[Dr ln(Dr)] indeed (by induction): c(n) = 19 10 n ln n ± O(n). Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
113. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) =1 3 r=1 E[Dr] + αn =−E[H base e Shannon entropy of D (D)] 3 r=1 E[Dr ln(Dr)] indeed (by induction): c(n) = 19 10 n ln n ± O(n). Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
114. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) =1 3 r=1 E[Dr] + αn =−E[H base e Shannon entropy of D (D)] 3 r=1 E[Dr ln(Dr)] ⇐⇒ α = 19 12 E[H(D)] indeed (by induction): c(n) = 19 10 n ln n ± O(n). Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
115. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) =1 3 r=1 E[Dr] + αn =−E[H base e Shannon entropy of D (D)] 3 r=1 E[Dr ln(Dr)] ⇐⇒ α = 19 12 E[H(D)] 5 6 indeed (by induction): c(n) = 19 10 n ln n ± O(n). Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
116. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) =1 3 r=1 E[Dr] + αn =−E[H base e Shannon entropy of D (D)] 3 r=1 E[Dr ln(Dr)] ⇐⇒ α = 19 12 E[H(D)] 5 6 = 19 10 indeed (by induction): c(n) = 19 10 n ln n ± O(n). Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
117. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) =1 3 r=1 E[Dr] + αn =−E[H base e Shannon entropy of D (D)] 3 r=1 E[Dr ln(Dr)] ⇐⇒ α = 19 12 E[H(D)] 5 6 = 19 10 indeed (by induction): c(n) = 19 10 n ln n ± O(n). Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
118. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) =1 3 r=1 E[Dr] + αn =−E[H base e Shannon entropy of D (D)] 3 r=1 E[Dr ln(Dr)] ⇐⇒ α = 19 12 E[H(D)] 5 6 = 19 10 indeed (by i Salvador Roura’s Continuous Master Theorem nduction): c(n) = 19 10 n ln n ± O(n). Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
119. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) =1 3 r=1 E[Dr] + αn =−E[H base e Shannon entropy of D (D)] 3 r=1 E[Dr ln(Dr)] ⇐⇒ α = 19 12 E[H(D)] 5 6 = 19 10 indeed (by i Salvador Roura’s Continuous Master Theorem nduction): c(n) = 19 10 n ln n ± O(n). Why does Shannon entropy show up here? Must learn ld(n!) ∼ n ld n bits of information to sort. For fixed D, one classification ( small / medium / large ) yields Hld (D) = − 3 r=1 Dr ld(Dr) bits of information costs a = 2 − E[ D3 D3 ] − E[ D1 (D1 + D2) ] = 19 12 cmps Average information yield: I = E[Hld (D)] a bits per comparison Need ld(n!) I ∼ a E[Hld (D)] n ld n = a E[H(D)] n ln n cmps! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
120. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) =1 3 r=1 E[Dr] + αn =−E[H base e Shannon entropy of D (D)] 3 r=1 E[Dr ln(Dr)] ⇐⇒ α = 19 12 E[H(D)] 5 6 = 19 10 indeed (by i Salvador Roura’s Continuous Master Theorem nduction): c(n) = 19 10 n ln n ± O(n). Why does Shannon entropy show up here? Must learn ld log2 (n!) ∼ n ld n bits of information to sort. For fixed D, one classification ( small / medium / large ) yields Hld (D) = − 3 r=1 Dr ld(Dr) bits of information costs a = 2 − E[ D3 D3 ] − E[ D1 (D1 + D2) ] = 19 12 cmps Average information yield: I = E[Hld (D)] a bits per comparison Need ld(n!) I ∼ a E[Hld (D)] n ld n = a E[H(D)] n ln n cmps! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
121. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) =1 3 r=1 E[Dr] + αn =−E[H base e Shannon entropy of D (D)] 3 r=1 E[Dr ln(Dr)] ⇐⇒ α = 19 12 E[H(D)] 5 6 = 19 10 indeed (by i Salvador Roura’s Continuous Master Theorem nduction): c(n) = 19 10 n ln n ± O(n). Why does Shannon entropy show up here? Must learn ld(n!) ∼ n ld n bits of information to sort. For fixed D, one classification ( small / medium / large ) yields Hld (D) = − 3 r=1 Dr ld(Dr) bits of information costs a = 2 − E[ D3 D3 ] − E[ D1 (D1 + D2) ] = 19 12 cmps Average information yield: I = E[Hld (D)] a bits per comparison Need ld(n!) I ∼ a E[Hld (D)] n ld n = a E[H(D)] n ln n cmps! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
122. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) =1 3 r=1 E[Dr] + αn =−E[H base e Shannon entropy of D (D)] 3 r=1 E[Dr ln(Dr)] ⇐⇒ α = 19 12 E[H(D)] 5 6 = 19 10 indeed (by i Salvador Roura’s Continuous Master Theorem nduction): c(n) = 19 10 n ln n ± O(n). Why does Shannon entropy show up here? Must learn ld(n!) ∼ n ld n bits of information to sort. For fixed D, one classification ( small / medium / large ) yields Hld binary entropy (D) = − 3 r=1 Dr ld(Dr) bits of information costs a = 2 − E[ D3 D3 ] − E[ D1 (D1 + D2) ] = 19 12 cmps Average information yield: I = E[Hld (D)] a bits per comparison Need ld(n!) I ∼ a E[Hld (D)] n ld n = a E[H(D)] n ln n cmps! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
123. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) =1 3 r=1 E[Dr] + αn =−E[H base e Shannon entropy of D (D)] 3 r=1 E[Dr ln(Dr)] ⇐⇒ α = 19 12 E[H(D)] 5 6 = 19 10 indeed (by i Salvador Roura’s Continuous Master Theorem nduction): c(n) = 19 10 n ln n ± O(n). Why does Shannon entropy show up here? Must learn ld(n!) ∼ n ld n bits of information to sort. For fixed D, one classification ( small / medium / large ) yields Hld binary entropy (D) = − 3 r=1 Dr ld(Dr) bits of information definition of entropy! costs a = 2 − E[ D3 D3 ] − E[ D1 (D1 + D2) ] = 19 12 cmps Average information yield: I = E[Hld (D)] a bits per comparison Need ld(n!) I ∼ a E[Hld (D)] n ld n = a E[H(D)] n ln n cmps! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
124. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) =1 3 r=1 E[Dr] + αn =−E[H base e Shannon entropy of D (D)] 3 r=1 E[Dr ln(Dr)] ⇐⇒ α = 19 12 E[H(D)] 5 6 = 19 10 indeed (by i Salvador Roura’s Continuous Master Theorem nduction): c(n) = 19 10 n ln n ± O(n). Why does Shannon entropy show up here? Must learn ld(n!) ∼ n ld n bits of information to sort. For fixed D, one classification ( small / medium / large ) yields Hld binary entropy (D) = − 3 r=1 Dr ld(Dr) bits of information definition of entropy! costs a = 2 − E[ D3 D3 ] − E[ D1 (D1 + D2) ] = 19 12 cmps Average information yield: I = E[Hld (D)] a bits per comparison Need ld(n!) I ∼ a E[Hld (D)] n ld n = a E[H(D)] n ln n cmps! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
125. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) =1 3 r=1 E[Dr] + αn =−E[H base e Shannon entropy of D (D)] 3 r=1 E[Dr ln(Dr)] ⇐⇒ α = 19 12 E[H(D)] 5 6 = 19 10 indeed (by i Salvador Roura’s Continuous Master Theorem nduction): c(n) = 19 10 n ln n ± O(n). Why does Shannon entropy show up here? Must learn ld(n!) ∼ n ld n bits of information to sort. For fixed D, one classification ( small / medium / large ) yields Hld binary entropy (D) = − 3 r=1 Dr ld(Dr) bits of information definition of entropy! costs a = 2 − E[ D3 D3 ] − E[ D1 (D1 + D2) ] = 19 12 cmps Average information yield: I = E[Hld (D)] a bits per comparison Need ld(n!) I ∼ a E[Hld (D)] n ld n = a E[H(D)] n ln n cmps! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
126. Recurrence c(n): E[#cmps] for sorting c(n) = t(n) + E c(I1) + E c(I2) + E c(I3) = 19 12 n + E c( D1 · n) + E c( D2 · n) + E c( D3 · n) ± O(n1/2+ε) Solve recurrence without error term by ansatz: c(n) = αnln(n) αn ln(n) = 19 12 n + αn ln(n) =1 3 r=1 E[Dr] + αn =−E[H base e Shannon entropy of D (D)] 3 r=1 E[Dr ln(Dr)] ⇐⇒ α = 19 12 E[H(D)] 5 6 = 19 10 indeed (by i Salvador Roura’s Continuous Master Theorem nduction): c(n) = 19 10 n ln n ± O(n). Why does Shannon entropy show up here? Must learn ld(n!) ∼ n ld n bits of information to sort. For fixed D, one classification ( small / medium / large ) yields Hld binary entropy (D) = − 3 r=1 Dr ld(Dr) bits of information definition of entropy! costs a = 2 − E[ D3 D3 ] − E[ D1 (D1 + D2) ] = 19 12 cmps Average information yield: I = E[Hld (D)] a bits per comparison Need ld(n!) I ∼ a E[Hld (D)] n ld n = a E[H(D)] n ln n cmps! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 10 / 22
127. Classic vs. YBB Quicksort Time for the competition! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 11 / 22
128. Classic vs. YBB Quicksort Time for the competition! CQS YQS Relative Running Time (from various experiments) −10±2% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 11 / 22
129. Classic vs. YBB Quicksort Time for the competition! CQS YQS Relative Running Time (from various experiments) −10±2% Comparisons 1.9 ·n ln n + O(n) , average case results Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 11 / 22
130. Classic vs. YBB Quicksort Time for the competition! CQS YQS Relative Running Time (from various experiments) −10±2% Comparisons 2 1.9 −5% ·n ln n + O(n) , average case results Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 11 / 22
131. Classic vs. YBB Quicksort Time for the competition! CQS YQS Relative Running Time (from various experiments) −10±2% Comparisons 2 1.9 −5% ·n ln n + O(n) , average case results Results for random pivots ... Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 11 / 22
132. Classic vs. YBB Quicksort Time for the competition! CQS YQS Relative Running Time (from various experiments) −10±2% Comparisons 2 1.9 −5% ·n ln n + O(n) , average case results Results for random pivots ... but Java 6/7 use pivot sampling: Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 11 / 22
133. Classic vs. YBB Quicksort Time for the competition! CQS YQS Relative Running Time (from various experiments) −10±2% Comparisons 2 1.9 −5% ·n ln n + O(n) , average case results Results for random pivots ... but Java 6/7 use pivot sampling: Java 6: Ninther pseudomedian of 9 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 11 / 22
134. Classic vs. YBB Quicksort Time for the competition! CQS YQS Relative Running Time (from various experiments) −10±2% Comparisons 2 1.9 −5% ·n ln n + O(n) , average case results Results for random pivots ... but Java 6/7 use pivot sampling: Java 6: Ninther Java 7: Tertiles of 5 pseudomedian of 9 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 11 / 22
135. Classic vs. YBB Quicksort Time for the competition! CQS YQS Relative Running Time (from various experiments) −10±2% Comparisons 2 1.9 −5% ·n ln n + O(n) , average case results Results for random pivots ... but Java 6/7 use pivot sampling: Java 6: Ninther Java 7: Tertiles of 5 pseudomedian of 9 How to analyze that? Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 11 / 22
136. Pivot Sampling Setup: Sampling parameter t = (t1, t2, t3) 1 Sample k = t1 + t2 + t3 + 2 elements 2 Sort the sample 3 Select pivots s. t. in sorted sample t1 smaller , t2 between and t3 larger than pivots tertiles of 5: t = (1, 1, 1) no pivot sampling: t = (0, 0, 0) not necessarily symmetric: t = (3, 2, 1) (k = 8): P Q t1 t2 t3 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 12 / 22
137. Pivot Sampling Setup: Sampling parameter t = (t1, t2, t3) 1 Sample k = t1 + t2 + t3 + 2 elements 2 Sort the sample 3 Select pivots s. t. in sorted sample t1 smaller , t2 between and t3 larger than pivots tertiles of 5: t = (1, 1, 1) no pivot sampling: t = (0, 0, 0) not necessarily symmetric: t = (3, 2, 1) (k = 8): P Q t1 t2 t3 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 12 / 22
138. Pivot Sampling Setup: Sampling parameter t = (t1, t2, t3) 1 Sample k = t1 + t2 + t3 + 2 elements 2 Sort the sample 3 Select pivots s. t. in sorted sample t1 smaller , t2 between and t3 larger than pivots tertiles of 5: t = (1, 1, 1) no pivot sampling: t = (0, 0, 0) not necessarily symmetric: t = (3, 2, 1) (k = 8): P Q t1 t2 t3 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 12 / 22
139. Pivot Sampling Setup: Sampling parameter t = (t1, t2, t3) 1 Sample k = t1 + t2 + t3 + 2 elements 2 Sort the sample 3 Select pivots s. t. in sorted sample t1 smaller , t2 between and t3 larger than pivots tertiles of 5: t = (1, 1, 1) no pivot sampling: t = (0, 0, 0) not necessarily symmetric: t = (3, 2, 1) (k = 8): P Q t1 t2 t3 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 12 / 22
140. Pivot Sampling Setup: Sampling parameter t = (t1, t2, t3) 1 Sample k = t1 + t2 + t3 + 2 elements 2 Sort the sample 3 Select pivots s. t. in sorted sample t1 smaller , t2 between and t3 larger than pivots tertiles of 5: t = (1, 1, 1) no pivot sampling: t = (0, 0, 0) not necessarily symmetric: t = (3, 2, 1) (k = 8): P Q t1 t2 t3 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 12 / 22
141. Pivot Sampling Setup: Sampling parameter t = (t1, t2, t3) 1 Sample k = t1 + t2 + t3 + 2 elements 2 Sort the sample 3 Select pivots s. t. in sorted sample t1 smaller , t2 between and t3 larger than pivots tertiles of 5: t = (1, 1, 1) no pivot sampling: t = (0, 0, 0) not necessarily symmetric: t = (3, 2, 1) (k = 8): P Q t1 t2 t3 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 12 / 22
142. Pivot Sampling Setup: Sampling parameter t = (t1, t2, t3) 1 Sample k = t1 + t2 + t3 + 2 elements 2 Sort the sample 3 Select pivots s. t. in sorted sample t1 smaller , t2 between and t3 larger than pivots tertiles of 5: t = (1, 1, 1) no pivot sampling: t = (0, 0, 0) not necessarily symmetric: t = (3, 2, 1) (k = 8): P Q t1 t2 t3 Analysis: Only distribution of D changes: D D = Dirichlet(t + 1) We still have c(n) ∼ 2 − E[D2 3 ] − E[D1(D1 + D2)] E[H(D)] · n ln n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 12 / 22
143. Pivot Sampling Setup: Sampling parameter t = (t1, t2, t3) 1 Sample k = t1 + t2 + t3 + 2 elements 2 Sort the sample 3 Select pivots s. t. in sorted sample t1 smaller , t2 between and t3 larger than pivots tertiles of 5: t = (1, 1, 1) no pivot sampling: t = (0, 0, 0) not necessarily symmetric: t = (3, 2, 1) (k = 8): P Q t1 t2 t3 Analysis: Only distribution of D changes: D D = Dirichlet multivariate Beta distribution (t + 1) We still have c(n) ∼ 2 − E[D2 3 ] − E[D1(D1 + D2)] E[H(D)] · n ln n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 12 / 22
144. Pivot Sampling Setup: Sampling parameter t = (t1, t2, t3) 1 Sample k = t1 + t2 + t3 + 2 elements 2 Sort the sample 3 Select pivots s. t. in sorted sample t1 smaller , t2 between and t3 larger than pivots tertiles of 5: t = (1, 1, 1) no pivot sampling: t = (0, 0, 0) not necessarily symmetric: t = (3, 2, 1) (k = 8): P Q t1 t2 t3 Analysis: Only distribution of D changes: D D = Dirichlet multivariate Beta distribution (t + 1) We still have c(n) ∼ 2 − E[D2 3 ] − E[D1(D1 + D2)] E[H(D)] · n ln n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 12 / 22
145. Pivot Sampling Setup: Sampling parameter t = (t1, t2, t3) 1 Sample k = t1 + t2 + t3 + 2 elements 2 Sort the sample 3 Select pivots s. t. in sorted sample t1 smaller , t2 between and t3 larger than pivots tertiles of 5: t = (1, 1, 1) no pivot sampling: t = (0, 0, 0) not necessarily symmetric: t = (3, 2, 1) (k = 8): P Q t1 t2 t3 Analysis: Only distribution of D changes: D D = Dirichlet multivariate Beta distribution (t + 1) We still have c(n) ∼ 2 − E[D2 3 ] − E[D1(D1 + D2)] E[H(D)] · n ln n = 1 + t2+1 k+1 + (2t1+t2+3)(t3+1) (k+2)(k+1) 3 r=1 tr+1 k+1 (Hk+1 − Htr+1) · n ln n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 12 / 22
146. Pivot Sampling Setup: Sampling parameter t = (t1, t2, t3) 1 Sample k = t1 + t2 + t3 + 2 elements 2 Sort the sample 3 Select pivots s. t. in sorted sample t1 smaller , t2 between and t3 larger than pivots tertiles of 5: t = (1, 1, 1) no pivot sampling: t = (0, 0, 0) not necessarily symmetric: t = (3, 2, 1) (k = 8): P Q t1 t2 t3 Analysis: Only distribution of D changes: D D = Dirichlet multivariate Beta distribution (t + 1) We still have c(n) ∼ 2 − E[D2 3 ] − E[D1(D1 + D2)] E[H(D)] · n ln n = 1 + t2+1 k+1 + (2t1+t2+3)(t3+1) (k+2)(k+1) 3 r=1 tr+1 k+1 (Hk+1 − Htr+1) · n ln n Interesting phenomenon 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 k = ∞ t1 + 1 k + 1 t2 + 1 k + 1 1.44 3 2 2.5 1.5 1.4931 Optimal sampling not symmetric. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 12 / 22
147. Pivot Sampling Setup: Sampling parameter t = (t1, t2, t3) 1 Sample k = t1 + t2 + t3 + 2 elements 2 Sort the sample 3 Select pivots s. t. in sorted sample t1 smaller , t2 between and t3 larger than pivots tertiles of 5: t = (1, 1, 1) no pivot sampling: t = (0, 0, 0) not necessarily symmetric: t = (3, 2, 1) (k = 8): P Q t1 t2 t3 Analysis: Only distribution of D changes: D D = Dirichlet multivariate Beta distribution (t + 1) We still have c(n) ∼ 2 − E[D2 3 ] − E[D1(D1 + D2)] E[H(D)] · n ln n = 1 + t2+1 k+1 + (2t1+t2+3)(t3+1) (k+2)(k+1) 3 r=1 tr+1 k+1 (Hk+1 − Htr+1) · n ln n Interesting phenomenon 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 k = ∞ (0.429, 0.269, 0.302) t1 + 1 k + 1 t2 + 1 k + 1 1.44 3 2 2.5 1.5 1.4931 1.5171 Optimal sampling not symmetric. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 12 / 22
148. Pivot Sampling Setup: Sampling parameter t = (t1, t2, t3) 1 Sample k = t1 + t2 + t3 + 2 elements 2 Sort the sample 3 Select pivots s. t. in sorted sample t1 smaller , t2 between and t3 larger than pivots tertiles of 5: t = (1, 1, 1) no pivot sampling: t = (0, 0, 0) not necessarily symmetric: t = (3, 2, 1) (k = 8): P Q t1 t2 t3 Analysis: Only distribution of D changes: D D = Dirichlet multivariate Beta distribution (t + 1) We still have c(n) ∼ 2 − E[D2 3 ] − E[D1(D1 + D2)] E[H(D)] · n ln n = 1 + t2+1 k+1 + (2t1+t2+3)(t3+1) (k+2)(k+1) 3 r=1 tr+1 k+1 (Hk+1 − Htr+1) · n ln n Java 7: t = (1, 1, 1) c(n) ∼ 680 399 n ln n ≈ 1.70426 n ln n Interesting phenomenon 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 k = ∞ (0.429, 0.269, 0.302) t1 + 1 k + 1 t2 + 1 k + 1 1.44 3 2 2.5 1.5 1.4931 1.5171 Optimal sampling not symmetric. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 12 / 22
149. Pivot Sampling Setup: Sampling parameter t = (t1, t2, t3) 1 Sample k = t1 + t2 + t3 + 2 elements 2 Sort the sample 3 Select pivots s. t. in sorted sample t1 smaller , t2 between and t3 larger than pivots tertiles of 5: t = (1, 1, 1) no pivot sampling: t = (0, 0, 0) not necessarily symmetric: t = (3, 2, 1) (k = 8): P Q t1 t2 t3 Analysis: Only distribution of D changes: D D = Dirichlet multivariate Beta distribution (t + 1) We still have c(n) ∼ 2 − E[D2 3 ] − E[D1(D1 + D2)] E[H(D)] · n ln n = 1 + t2+1 k+1 + (2t1+t2+3)(t3+1) (k+2)(k+1) 3 r=1 tr+1 k+1 (Hk+1 − Htr+1) · n ln n Java 7: t = (1, 1, 1) c(n) ∼ 680 399 n ln n ≈ 1.70426 n ln n Interesting phenomenon 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 k = ∞ (0.429, 0.269, 0.302) t1 + 1 k + 1 t2 + 1 k + 1 1.44 3 2 2.5 1.5 1.4931 1.5171 Optimal sampling not symmetric. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 12 / 22
150. Classic vs. YBB Quicksort Time for the competition! CQS YQS Relative Running Time (from various experiments) −10±2% Comparisons 2 1.9 −5% ·n ln n + O(n) , average case results Results for random pivots ... but Java 6/7 use pivot sampling: Java 6: Ninther Java 7: Tertiles of 5 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 13 / 22
151. Classic vs. YBB Quicksort Time for the competition! CQS YQS Relative Running Time (from various experiments) −10±2% Comparisons 2 1.9 −5% (with sampling as in JRE) 1.70 ·n ln n + O(n) , average case results Results for random pivots ... but Java 6/7 use pivot sampling: Java 6: Ninther Java 7: Tertiles of 5 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 13 / 22
152. Classic vs. YBB Quicksort Time for the competition! CQS YQS Relative Running Time (from various experiments) −10±2% Comparisons 2 1.9 −5% (with sampling as in JRE) 1.57 1.70 +8.6% ·n ln n + O(n) , average case results Results for random pivots ... but Java 6/7 use pivot sampling: Java 6: Ninther Java 7: Tertiles of 5 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 13 / 22
153. Classic vs. YBB Quicksort Time for the competition! CQS YQS Relative Running Time (from various experiments) −10±2% Comparisons 2 1.9 −5% (with sampling as in JRE) 1.57 1.70 +8.6% Swaps 0.3 0.6 +80% ·n ln n + O(n) , average case results Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 13 / 22
154. Classic vs. YBB Quicksort Time for the competition! CQS YQS Relative Running Time (from various experiments) −10±2% Comparisons 2 1.9 −5% (with sampling as in JRE) 1.57 1.70 +8.6% Swaps 0.3 0.6 +80% Bytecode Instructions 18 21.7 +20.6% MMIX Knuth’s mythical machine oops υ 11 13.1 +19.1% MMIX mems µ 2.6 2.8 +5% ·n ln n + O(n) , average case results Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 13 / 22
155. Classic vs. YBB Quicksort Time for the competition! CQS YQS Relative Running Time (from various experiments) −10±2% Comparisons 2 1.9 −5% (with sampling as in JRE) 1.57 1.70 +8.6% Swaps 0.3 0.6 +80% Bytecode Instructions 18 21.7 +20.6% MMIX Knuth’s mythical machine oops υ 11 13.1 +19.1% MMIX mems µ 2.6 2.8 +5% Branch Mispredictions 0.57 0.58 +2% ·n ln n + O(n) , average case results Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 13 / 22
156. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
157. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
158. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. 1991 1995 2000 2005 2010 2015 100 102 104 106 CPU speed (MFLOPS) STREAM benchmark data with linear regressions www.cs.virginia.edu/stream/by_date/Balance.html Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
159. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. 1991 1995 2000 2005 2010 2015 100 102 104 106 CPU speed (MFLOPS) STREAM benchmark data with linear regressions www.cs.virginia.edu/stream/by_date/Balance.html Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
160. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. 1991 1995 2000 2005 2010 2015 100 102 104 106 CPU speed (MFLOPS) STREAM benchmark data with linear regressions www.cs.virginia.edu/stream/by_date/Balance.html Averaged annual growth rates: Processor speed: 46% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
161. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. 1991 1995 2000 2005 2010 2015 100 102 104 106 CPU speed (MFLOPS) RAM bandwidth (MWords/s) STREAM benchmark data with linear regressions www.cs.virginia.edu/stream/by_date/Balance.html Averaged annual growth rates: Processor speed: 46% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
162. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. 1991 1995 2000 2005 2010 2015 100 102 104 106 CPU speed (MFLOPS) RAM bandwidth (MWords/s) STREAM benchmark data with linear regressions www.cs.virginia.edu/stream/by_date/Balance.html Averaged annual growth rates: Processor speed: 46% Memory Bandwidth: 37% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
163. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. 1991 1995 2000 2005 2010 2015 100 102 104 106 CPU speed (MFLOPS) RAM bandwidth (MWords/s) STREAM benchmark data with linear regressions www.cs.virginia.edu/stream/by_date/Balance.html Averaged annual growth rates: Processor speed: 46% Memory Bandwidth: 37% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
164. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. 1991 1995 2000 2005 2010 2015 100 102 104 106 growing gap CPU speed (MFLOPS) RAM bandwidth (MWords/s) STREAM benchmark data with linear regressions www.cs.virginia.edu/stream/by_date/Balance.html Averaged annual growth rates: Processor speed: 46% Memory Bandwidth: 37% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
165. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. 1991 1995 2000 2005 2010 2015 100 102 104 106 growing gap CPU speed (MFLOPS) RAM bandwidth (MWords/s) “imbalance”: speed bandwidth STREAM benchmark data with linear regressions www.cs.virginia.edu/stream/by_date/Balance.html Averaged annual growth rates: Processor speed: 46% Memory Bandwidth: 37% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
166. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. 1991 1995 2000 2005 2010 2015 100 101 102 CPU speed (MFLOPS) RAM bandwidth (MWords/s) “imbalance”: speed bandwidth STREAM benchmark data with linear regressions www.cs.virginia.edu/stream/by_date/Balance.html Averaged annual growth rates: Processor speed: 46% Memory Bandwidth: 37% Imbalance: 5% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
167. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. 1991 1995 2000 2005 2010 2015 100 101 102 CPU speed (MFLOPS) RAM bandwidth (MWords/s) “imbalance”: speed bandwidth STREAM benchmark data with linear regressions www.cs.virginia.edu/stream/by_date/Balance.html Averaged annual growth rates: Processor speed: 46% Memory Bandwidth: 37% Imbalance: 5% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
168. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. 1991 1995 2000 2005 2010 2015 100 101 102 CPU speed (MFLOPS) RAM bandwidth (MWords/s) “imbalance”: speed bandwidth STREAM benchmark data with linear regressions www.cs.virginia.edu/stream/by_date/Balance.html Averaged annual growth rates: Processor speed: 46% Memory Bandwidth: 37% Imbalance: 5% Classic Quicksort (Bentley & McIlroy) 1993 1 mem. transfer ≈ 7 operations optimized for CPU Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
169. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. 1991 1995 2000 2005 2010 2015 100 101 102 CPU speed (MFLOPS) RAM bandwidth (MWords/s) “imbalance”: speed bandwidth STREAM benchmark data with linear regressions www.cs.virginia.edu/stream/by_date/Balance.html Averaged annual growth rates: Processor speed: 46% Memory Bandwidth: 37% Imbalance: 5% Classic Quicksort (Bentley & McIlroy) 1993 1 mem. transfer ≈ 7 operations optimized for CPU Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
170. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. 1991 1995 2000 2005 2010 2015 100 101 102 CPU speed (MFLOPS) RAM bandwidth (MWords/s) “imbalance”: speed bandwidth STREAM benchmark data with linear regressions www.cs.virginia.edu/stream/by_date/Balance.html Averaged annual growth rates: Processor speed: 46% Memory Bandwidth: 37% Imbalance: 5% Classic Quicksort (Bentley & McIlroy) 1993 1 mem. transfer ≈ 7 operations optimized for CPU Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
171. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. 1991 1995 2000 2005 2010 2015 100 101 102 CPU speed (MFLOPS) RAM bandwidth (MWords/s) “imbalance”: speed bandwidth STREAM benchmark data with linear regressions www.cs.virginia.edu/stream/by_date/Balance.html Averaged annual growth rates: Processor speed: 46% Memory Bandwidth: 37% Imbalance: 5% Classic Quicksort (Bentley & McIlroy) 1993 1 mem. transfer ≈ 7 operations optimized for CPU Dual-Pivot Quicksort, 2009 – today 1 mem. transfer ≈ 30 operations optimize for CPU and bandwidth? Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
172. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. 1991 1995 2000 2005 2010 2015 100 101 102 CPU speed (MFLOPS) RAM bandwidth (MWords/s) “imbalance”: speed bandwidth STREAM benchmark data with linear regressions www.cs.virginia.edu/stream/by_date/Balance.html Averaged annual growth rates: Processor speed: 46% Memory Bandwidth: 37% Imbalance: 5% Classic Quicksort (Bentley & McIlroy) 1993 1 mem. transfer ≈ 7 operations optimized for CPU Dual-Pivot Quicksort, 2009 – today 1 mem. transfer ≈ 30 operations optimize for CPU and bandwidth? Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
173. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. 1991 1995 2000 2005 2010 2015 100 101 102 CPU speed (MFLOPS) RAM bandwidth (MWords/s) “imbalance”: speed bandwidth STREAM benchmark data with linear regressions www.cs.virginia.edu/stream/by_date/Balance.html Averaged annual growth rates: Processor speed: 46% Memory Bandwidth: 37% Imbalance: 5% Classic Quicksort (Bentley & McIlroy) 1993 1 mem. transfer ≈ 7 operations optimized for CPU Dual-Pivot Quicksort, 2009 – today 1 mem. transfer ≈ 30 operations optimize for CPU and bandwidth? Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
174. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. 1991 1995 2000 2005 2010 2015 100 101 102 CPU speed (MFLOPS) RAM bandwidth (MWords/s) “imbalance”: speed bandwidth STREAM benchmark data with linear regressions www.cs.virginia.edu/stream/by_date/Balance.html Averaged annual growth rates: Processor speed: 46% Memory Bandwidth: 37% Imbalance: 5% Classic Quicksort (Bentley & McIlroy) 1993 1 mem. transfer ≈ 7 operations optimized for CPU Dual-Pivot Quicksort, 2009 – today 1 mem. transfer ≈ 30 operations optimize for CPU and bandwidth? Why did no-one use dual-pivot Quicksort earlier? Because it was not faster! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
175. The Memory Wall Comparisons = CPU effort, but we also need to load items from memory. 1991 1995 2000 2005 2010 2015 100 101 102 CPU speed (MFLOPS) RAM bandwidth (MWords/s) “imbalance”: speed bandwidth STREAM benchmark data with linear regressions www.cs.virginia.edu/stream/by_date/Balance.html Averaged annual growth rates: Processor speed: 46% Memory Bandwidth: 37% Imbalance: 5% Classic Quicksort (Bentley & McIlroy) 1993 1 mem. transfer ≈ 7 operations optimized for CPU Dual-Pivot Quicksort, 2009 – today 1 mem. transfer ≈ 30 operations optimize for CPU and bandwidth? Why did no-one use dual-pivot Quicksort earlier? Because it was not faster! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 14 / 22
176. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
177. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
178. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Why reinvent the wheel? I/Os in external-memory model additional parameters M and B typically: O(◦), only I/Os count cache misses hardware-specific misses vs. bandwidth Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
179. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Why reinvent the wheel? I/Os in external-memory model additional parameters M and B typically: O(◦), only I/Os count cache misses hardware-specific misses vs. bandwidth Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
180. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Why reinvent the wheel? I/Os in external-memory model additional parameters M and B typically: O(◦), only I/Os count cache misses hardware-specific misses vs. bandwidth Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
181. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Why reinvent the wheel? I/Os in external-memory model additional parameters M and B typically: O(◦), only I/Os count cache misses hardware-specific misses vs. bandwidth Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
182. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Why reinvent the wheel? I/Os in external-memory model additional parameters M and B typically: O(◦), only I/Os count cache misses hardware-specific misses vs. bandwidth Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
183. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Why reinvent the wheel? I/Os in external-memory model additional parameters M and B typically: O(◦), only I/Os count cache misses hardware-specific misses vs. bandwidth Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
184. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Why reinvent the wheel? I/Os in external-memory model additional parameters M and B typically: O(◦), only I/Os count cache misses hardware-specific misses vs. bandwidth Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
185. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Why reinvent the wheel? I/Os in external-memory model additional parameters M and B typically: O(◦), only I/Os count cache misses hardware-specific misses vs. bandwidth Proposal: count scanned elements Access to array only through iterators (no random access!) 5 1 1 2 7 3 4 4 2 5 8 6 Iterators can head left or right (one-directional!) advance to next position read and write current cell Cost: number of advances ≈ cache misses, but hardware independent Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
186. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Why reinvent the wheel? I/Os in external-memory model additional parameters M and B typically: O(◦), only I/Os count cache misses hardware-specific misses vs. bandwidth Proposal: count scanned elements Access to array only through iterators (no random access!) 5 1 1 2 7 3 4 4 2 5 8 6 Iterators can head left or right (one-directional!) advance to next position read and write current cell Cost: number of advances ≈ cache misses, but hardware independent Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
187. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Why reinvent the wheel? I/Os in external-memory model additional parameters M and B typically: O(◦), only I/Os count cache misses hardware-specific misses vs. bandwidth Proposal: count scanned elements Access to array only through iterators (no random access!) 5 1 1 2 7 3 4 4 2 5 8 6 Iterators can head left or right (one-directional!) advance to next position read and write current cell Cost: number of advances ≈ cache misses, but hardware independent Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
188. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Why reinvent the wheel? I/Os in external-memory model additional parameters M and B typically: O(◦), only I/Os count cache misses hardware-specific misses vs. bandwidth Proposal: count scanned elements Access to array only through iterators (no random access!) 5 1 1 2 7 3 4 4 2 5 8 6 Iterators can head left or right (one-directional!) advance to next position read and write current cell Cost: number of advances ≈ cache misses, but hardware independent Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
189. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Why reinvent the wheel? I/Os in external-memory model additional parameters M and B typically: O(◦), only I/Os count cache misses hardware-specific misses vs. bandwidth Proposal: count scanned elements Access to array only through iterators (no random access!) 5 1 1 2 7 3 4 4 2 5 8 6 Iterators can head left or right (one-directional!) advance to next position read and write current cell Cost: number of advances ≈ cache misses, but hardware independent Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
190. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Why reinvent the wheel? I/Os in external-memory model additional parameters M and B typically: O(◦), only I/Os count cache misses hardware-specific misses vs. bandwidth Proposal: count scanned elements Access to array only through iterators (no random access!) 5 1 1 2 7 3 4 4 2 5 8 6 Iterators can head left or right (one-directional!) advance to next position read and write current cell Cost: number of advances ≈ cache misses, but hardware independent Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
191. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Why reinvent the wheel? I/Os in external-memory model additional parameters M and B typically: O(◦), only I/Os count cache misses hardware-specific misses vs. bandwidth Proposal: count scanned elements Access to array only through iterators (no random access!) 5 1 1 2 7 3 4 4 2 5 8 6 Iterators can head left or right (one-directional!) advance to next position read and write current cell Cost: number of advances ≈ cache misses, but hardware independent Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
192. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Why reinvent the wheel? I/Os in external-memory model additional parameters M and B typically: O(◦), only I/Os count cache misses hardware-specific misses vs. bandwidth Proposal: count scanned elements Access to array only through iterators (no random access!) 5 1 1 2 7 3 4 4 2 5 8 6 Iterators can head left or right (one-directional!) advance to next position read and write current cell Cost: number of advances ≈ cache misses, but hardware independent Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
193. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Proposal: count scanned elements Access to array only through iterators (no random access!) 5 1 1 2 7 3 4 4 2 5 8 6 Iterators can head left or right (one-directional!) advance to next position read and write current cell Cost: number of advances ≈ cache misses, but hardware independent Costs of Partitioning Classic Quicksort k g n scanned elements (array scanned once) YBB Quicksort k g 1.3n scanned elements (on average without sampling) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
194. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Proposal: count scanned elements Access to array only through iterators (no random access!) 5 1 1 2 7 3 4 4 2 5 8 6 Iterators can head left or right (one-directional!) advance to next position read and write current cell Cost: number of advances ≈ cache misses, but hardware independent Costs of Partitioning Classic Quicksort k g n scanned elements (array scanned once) YBB Quicksort k g 1.3n scanned elements (on average without sampling) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
195. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Proposal: count scanned elements Access to array only through iterators (no random access!) 5 1 1 2 7 3 4 4 2 5 8 6 Iterators can head left or right (one-directional!) advance to next position read and write current cell Cost: number of advances ≈ cache misses, but hardware independent Costs of Partitioning Classic Quicksort k g n scanned elements (array scanned once) YBB Quicksort k g 1.3n scanned elements (on average without sampling) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
196. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Proposal: count scanned elements Access to array only through iterators (no random access!) 5 1 1 2 7 3 4 4 2 5 8 6 Iterators can head left or right (one-directional!) advance to next position read and write current cell Cost: number of advances ≈ cache misses, but hardware independent Costs of Partitioning Classic Quicksort k g n scanned elements (array scanned once) YBB Quicksort k g 1.3n scanned elements (on average without sampling) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
197. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Proposal: count scanned elements Access to array only through iterators (no random access!) 5 1 1 2 7 3 4 4 2 5 8 6 Iterators can head left or right (one-directional!) advance to next position read and write current cell Cost: number of advances ≈ cache misses, but hardware independent Costs of Partitioning Classic Quicksort k g n scanned elements (array scanned once) YBB Quicksort k g 1.3n scanned elements (on average without sampling) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
198. Scanned Elements How to analyze bandwidth consumption? Need good cost measure! Proposal: count scanned elements Access to array only through iterators (no random access!) 5 1 1 2 7 3 4 4 2 5 8 6 Iterators can head left or right (one-directional!) advance to next position read and write current cell Cost: number of advances ≈ cache misses, but hardware independent Costs of Partitioning Classic Quicksort k g n scanned elements (array scanned once) YBB Quicksort k g 1.3 1 + E[D1 ] in general n scanned elements (on average without sampling) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 15 / 22
199. Classic vs. YBB Quicksort Time for the competition! CQS YQS Relative Running Time (from various experiments) −10±2% Comparisons 2 1.9 −5% (with sampling as in JRE) 1.57 1.70 +8.6% Swaps 0.3 0.6 +80% Bytecode Instructions 18 21.7 +20.6% MMIX oops υ 11 13.1 +19.1% MMIX mems µ 2.6 2.8 +5% Branch Mispredictions 0.57 0.58 +2% ·n ln n + O(n) , average case results Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 16 / 22
200. Classic vs. YBB Quicksort Time for the competition! CQS YQS Relative Running Time (from various experiments) −10±2% Comparisons 2 1.9 −5% (with sampling as in JRE) 1.57 1.70 +8.6% Swaps 0.3 0.6 +80% Bytecode Instructions 18 21.7 +20.6% MMIX oops υ 11 13.1 +19.1% MMIX mems µ 2.6 2.8 +5% Branch Mispredictions 0.57 0.58 +2% Scanned Elements 2 1.6 −20% ·n ln n + O(n) , average case results Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 16 / 22
201. Classic vs. YBB Quicksort Time for the competition! CQS YQS Relative Running Time (from various experiments) −10±2% Comparisons 2 1.9 −5% (with sampling as in JRE) 1.57 1.70 +8.6% Swaps 0.3 0.6 +80% Bytecode Instructions 18 21.7 +20.6% MMIX oops υ 11 13.1 +19.1% MMIX mems µ 2.6 2.8 +5% Branch Mispredictions 0.57 0.58 +2% Scanned Elements 2 1.6 −20% ·n ln n + O(n) , average case results Only plausible explanation for running time: 20% less memory transfers in YQS. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 16 / 22
202. Beyond Dual-Pivot: Multiway Partitioning Can we do even better than YBB Quicksort? Setup: Generic s-way one-pass partitioning s-way partitioning: split input into s 2 parts one pass over input m segments grow from left, s − m from right km k2 k ≡ k1 g ≡ g1 g2 gs−m sm . . . s1 ? l1 . . . ls−m . . . . . . left right classify elements using BSTs: λk and λg pivots P1, . . . , Ps−1 chosen from sample: t ∈ Ns 0 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 17 / 22
203. Beyond Dual-Pivot: Multiway Partitioning Can we do even better than YBB Quicksort? Setup: Generic s-way one-pass partitioning s-way partitioning: split input into s 2 parts one pass over input m segments grow from left, s − m from right km k2 k ≡ k1 g ≡ g1 g2 gs−m sm . . . s1 ? l1 . . . ls−m . . . . . . left right classify elements using BSTs: λk and λg pivots P1, . . . , Ps−1 chosen from sample: t ∈ Ns 0 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 17 / 22
204. Beyond Dual-Pivot: Multiway Partitioning Can we do even better than YBB Quicksort? Setup: Generic s-way one-pass partitioning s-way partitioning: split input into s 2 parts one pass over input m segments grow from left, s − m from right km k2 k ≡ k1 g ≡ g1 g2 gs−m sm . . . s1 ? l1 . . . ls−m . . . . . . left right classify elements using BSTs: λk and λg pivots P1, . . . , Ps−1 chosen from sample: t ∈ Ns 0 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 17 / 22
205. Beyond Dual-Pivot: Multiway Partitioning Can we do even better than YBB Quicksort? Setup: Generic s-way one-pass partitioning s-way partitioning: split input into s 2 parts one pass over input m segments grow from left, s − m from right km k2 k ≡ k1 g ≡ g1 g2 gs−m sm . . . s1 ? l1 . . . ls−m . . . . . . left right classify elements using BSTs: λk and λg pivots P1, . . . , Ps−1 chosen from sample: t ∈ Ns 0 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 17 / 22
206. Beyond Dual-Pivot: Multiway Partitioning Can we do even better than YBB Quicksort? Setup: Generic s-way one-pass partitioning s-way partitioning: split input into s 2 parts one pass over input m segments grow from left, s − m from right km k2 k ≡ k1 g ≡ g1 g2 gs−m sm . . . s1 ? l1 . . . ls−m . . . . . . left right classify elements using BSTs: λk and λg pivots P1, . . . , Ps−1 chosen from sample: t ∈ Ns 0 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 17 / 22
207. Beyond Dual-Pivot: Multiway Partitioning Can we do even better than YBB Quicksort? Setup: Generic s-way one-pass partitioning s-way partitioning: split input into s 2 parts one pass over input m segments grow from left, s − m from right km k2 k ≡ k1 g ≡ g1 g2 gs−m sm . . . s1 ? l1 . . . ls−m . . . . . . left right classify elements using BSTs: λk and λg pivots P1, . . . , Ps−1 chosen from sample: t ∈ Ns 0 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 17 / 22
208. Beyond Dual-Pivot: Multiway Partitioning Can we do even better than YBB Quicksort? Setup: Generic s-way one-pass partitioning s-way partitioning: split input into s 2 parts one pass over input m segments grow from left, s − m from right km k2 k ≡ k1 g ≡ g1 g2 gs−m sm . . . s1 ? l1 . . . ls−m . . . . . . left right classify elements using BSTs: λk and λg Quicksort variants as special cases Method s m λk λg pivots P1, . . . , Ps−1 chosen from sample: t ∈ Ns 0 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 17 / 22
209. Beyond Dual-Pivot: Multiway Partitioning Can we do even better than YBB Quicksort? Setup: Generic s-way one-pass partitioning s-way partitioning: split input into s 2 parts one pass over input m segments grow from left, s − m from right km k2 k ≡ k1 g ≡ g1 g2 gs−m sm . . . s1 ? l1 . . . ls−m . . . . . . left right classify elements using BSTs: λk and λg Quicksort variants as special cases Method s m λk λg Classic 2 1 < pivots P1, . . . , Ps−1 chosen from sample: t ∈ Ns 0 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 17 / 22
210. Beyond Dual-Pivot: Multiway Partitioning Can we do even better than YBB Quicksort? Setup: Generic s-way one-pass partitioning s-way partitioning: split input into s 2 parts one pass over input m segments grow from left, s − m from right km k2 k ≡ k1 g ≡ g1 g2 gs−m sm . . . s1 ? l1 . . . ls−m . . . . . . left right classify elements using BSTs: λk and λg Quicksort variants as special cases Method s m λk λg Classic 2 1 < Lomuto 2 2 pivots P1, . . . , Ps−1 chosen from sample: t ∈ Ns 0 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 17 / 22
211. Beyond Dual-Pivot: Multiway Partitioning Can we do even better than YBB Quicksort? Setup: Generic s-way one-pass partitioning s-way partitioning: split input into s 2 parts one pass over input m segments grow from left, s − m from right km k2 k ≡ k1 g ≡ g1 g2 gs−m sm . . . s1 ? l1 . . . ls−m . . . . . . left right classify elements using BSTs: λk and λg Quicksort variants as special cases Method s m λk λg Classic 2 1 < Lomuto 2 2 YBB 3 2 < < pivots P1, . . . , Ps−1 chosen from sample: t ∈ Ns 0 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 17 / 22
212. Beyond Dual-Pivot: Multiway Partitioning Can we do even better than YBB Quicksort? Setup: Generic s-way one-pass partitioning s-way partitioning: split input into s 2 parts one pass over input m segments grow from left, s − m from right km k2 k ≡ k1 g ≡ g1 g2 gs−m sm . . . s1 ? l1 . . . ls−m . . . . . . left right classify elements using BSTs: λk and λg Quicksort variants as special cases Method s m λk λg Classic 2 1 < Lomuto 2 2 YBB 3 2 < < Waterloo 4 2 < < < pivots P1, . . . , Ps−1 chosen from sample: t ∈ Ns 0 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 17 / 22
213. Beyond Dual-Pivot: Multiway Partitioning Can we do even better than YBB Quicksort? Setup: Generic s-way one-pass partitioning s-way partitioning: split input into s 2 parts one pass over input m segments grow from left, s − m from right km k2 k ≡ k1 g ≡ g1 g2 gs−m sm . . . s1 ? l1 . . . ls−m . . . . . . left right classify elements using BSTs: λk and λg Quicksort variants as special cases Method s m λk λg Classic 2 1 < Lomuto 2 2 YBB 3 2 < < Waterloo 4 2 < < < pivots P1, . . . , Ps−1 chosen from sample: t ∈ Ns 0 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 17 / 22
214. Beyond Dual-Pivot: Multiway Partitioning Can we do even better than YBB Quicksort? Setup: Generic s-way one-pass partitioning s-way partitioning: split input into s 2 parts one pass over input m segments grow from left, s − m from right km k2 k ≡ k1 g ≡ g1 g2 gs−m sm . . . s1 ? l1 . . . ls−m . . . . . . left right classify elements using BSTs: λk and λg Quicksort variants as special cases Method s m λk λg Classic 2 1 < Lomuto 2 2 YBB 3 2 < < Waterloo 4 2 < < < pivots P1, . . . , Ps−1 chosen from sample: t ∈ Ns 0 Same analysis techniques apply: c(n) ∼ E[#cmps to classify 1 element] E H(D) · n ln n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 17 / 22
215. Beyond Dual-Pivot: Multiway Partitioning Can we do even better than YBB Quicksort? Setup: Generic s-way one-pass partitioning s-way partitioning: split input into s 2 parts one pass over input m segments grow from left, s − m from right km k2 k ≡ k1 g ≡ g1 g2 gs−m sm . . . s1 ? l1 . . . ls−m . . . . . . left right classify elements using BSTs: λk and λg Quicksort variants as special cases Method s m λk λg Classic 2 1 < Lomuto 2 2 YBB 3 2 < < Waterloo 4 2 < < < pivots P1, . . . , Ps−1 chosen from sample: t ∈ Ns 0 Same analysis techniques apply: c(n) ∼ E[#cmps to classify 1 element] E H(D) · n ln n Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 17 / 22
216. Fair Competition? Consider the #comparisons again. 4-way Quicksort < < < <P2 <P1 c1 c2 <P3 c3 c4 Always need 2 cmps to classify. 24 13 ≈ 1.846 n ln(n) cmps (without sampling) Classic Quicksort 2 n ln(n) comparisons (without sampling) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 18 / 22
217. Fair Competition? Consider the #comparisons again. 4-way situation for YBB similar Quicksort < < < <P2 <P1 c1 c2 <P3 c3 c4 Always need 2 cmps to classify. 24 13 ≈ 1.846 n ln(n) cmps (without sampling) Classic Quicksort 2 n ln(n) comparisons (without sampling) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 18 / 22
218. Fair Competition? Consider the #comparisons again. 4-way situation for YBB similar Quicksort < < < <P2 <P1 c1 c2 <P3 c3 c4 Always need 2 cmps to classify. 24 13 ≈ 1.846 n ln(n) cmps (without sampling) Classic Quicksort 2 n ln(n) comparisons (without sampling) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 18 / 22
219. Fair Competition? Consider the #comparisons again. 4-way situation for YBB similar Quicksort < < < <P2 <P1 c1 c2 <P3 c3 c4 Always need 2 cmps to classify. 24 13 ≈ 1.846 n ln(n) cmps (without sampling) Classic Quicksort 2 n ln(n) comparisons (without sampling) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 18 / 22
220. Fair Competition? Consider the #comparisons again. 4-way situation for YBB similar Quicksort < < < <P2 <P1 c1 c2 <P3 c3 c4 Always need 2 cmps to classify. 24 13 ≈ 1.846 n ln(n) cmps (without sampling) vs. Classic Quicksort 2 n ln(n) comparisons (without sampling) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 18 / 22
221. Fair Competition? Consider the #comparisons again. 4-way situation for YBB similar Quicksort < < < <P2 <P1 c1 c2 <P3 c3 c4 Always need 2 cmps to classify. 24 13 ≈ 1.846 n ln(n) cmps (without sampling) vs. Classic Quicksort 2 n ln(n) comparisons (without sampling) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 18 / 22
222. Fair Competition? Consider the #comparisons again. 4-way situation for YBB similar Quicksort < < < <P2 <P1 c1 c2 <P3 c3 c4 Always need 2 cmps to classify. 24 13 ≈ 1.846 n ln(n) cmps (without sampling) vs. Classic Quicksort 2 n ln(n) comparisons (without sampling) Aha! Multiway Quicksort is better! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 18 / 22
223. Fair Competition? Consider the #comparisons again. 4-way situation for YBB similar Quicksort < < < <P2 <P1 c1 c2 <P3 c3 c4 Always need 2 cmps to classify. 24 13 ≈ 1.846 n ln(n) cmps (without sampling) vs. Classic Quicksort 2 n ln(n) comparisons (without sampling) Aha! Multiway Quicksort is better! 12 7 ≈ 1.714 n ln(n) comparisons (median-of-3) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 18 / 22
224. Fair Competition? Consider the #comparisons again. 4-way situation for YBB similar Quicksort < < < <P2 <P1 c1 c2 <P3 c3 c4 Always need 2 cmps to classify. 24 13 ≈ 1.846 n ln(n) cmps (without sampling) vs. Classic Quicksort 2 n ln(n) comparisons (without sampling) Aha! Multiway Quicksort is better! ...or not; it depends on sampling. 12 7 ≈ 1.714 n ln(n) comparisons (median-of-3) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 18 / 22
225. Fair Competition? Consider the #comparisons again. 4-way situation for YBB similar Quicksort < < < <P2 <P1 c1 c2 <P3 c3 c4 Always need 2 cmps to classify. 24 13 ≈ 1.846 n ln(n) cmps (without sampling) vs. Classic Quicksort 2 n ln(n) comparisons (without sampling) Aha! Multiway Quicksort is better! ...or not; it depends on sampling. 12 7 ≈ 1.714 n ln(n) comparisons (median-of-3) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 18 / 22
226. Fair Competition? Consider the #comparisons again. 4-way situation for YBB similar Quicksort < < < <P2 <P1 c1 c2 <P3 c3 c4 Always need 2 cmps to classify. 24 13 ≈ 1.846 n ln(n) cmps (without sampling) vs. Classic Quicksort 2 n ln(n) comparisons (without sampling) Aha! Multiway Quicksort is better! ...or not; it depends on sampling. 12 7 ≈ 1.714 n ln(n) comparisons (median-of-3) How to separate influence of multiway partitioning from that of sampling? Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 18 / 22
227. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
228. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
229. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
230. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
231. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
232. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
233. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
234. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
235. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
236. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 But how to choose pivots P1, P2, P3? Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
237. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 But how to choose pivots P1, P2, P3? P2 is chosen as median of 3! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
238. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 But how to choose pivots P1, P2, P3? P2 is chosen as median of 3! P1 and P3 uniform! Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
239. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 But how to choose pivots P1, P2, P3? P2 is chosen as median of 3! P1 and P3 uniform! can simulate 4-way partitioning exactly by alternating between median-of-3 and no sampling. same on average: 1 flip a fair coin 2 median-of-3 for heads no sampling for tails random-parameter pivot sampling Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
240. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 But how to choose pivots P1, P2, P3? P2 is chosen as median of 3! P1 and P3 uniform! can simulate 4-way partitioning exactly by alternating between median-of-3 and no sampling. same on average: 1 flip a fair coin 2 median-of-3 for heads no sampling for tails random-parameter pivot sampling Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
241. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 But how to choose pivots P1, P2, P3? P2 is chosen as median of 3! P1 and P3 uniform! can simulate 4-way partitioning exactly by alternating between median-of-3 and no sampling. same on average: 1 flip a fair coin 2 median-of-3 for heads no sampling for tails random-parameter pivot sampling Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
242. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 But how to choose pivots P1, P2, P3? P2 is chosen as median of 3! P1 and P3 uniform! can simulate 4-way partitioning exactly by alternating between median-of-3 and no sampling. same on average: 1 flip a fair coin 2 median-of-3 for heads no sampling for tails random-parameter pivot sampling Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
243. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 But how to choose pivots P1, P2, P3? P2 is chosen as median of 3! P1 and P3 uniform! can simulate 4-way partitioning exactly by alternating between median-of-3 and no sampling. same on average: 1 flip a fair coin 2 median-of-3 for heads no sampling for tails random-parameter pivot sampling Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
244. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 But how to choose pivots P1, P2, P3? P2 is chosen as median of 3! P1 and P3 uniform! can simulate 4-way partitioning exactly by alternating between median-of-3 and no sampling. same on average: 1 flip a fair coin 2 median-of-3 for heads no sampling for tails random-parameter pivot sampling Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
245. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 But how to choose pivots P1, P2, P3? P2 is chosen as median of 3! P1 and P3 uniform! can simulate 4-way partitioning exactly by alternating between median-of-3 and no sampling. same on average: 1 flip a fair coin 2 median-of-3 for heads no sampling for tails random-parameter pivot sampling Theorem (Entropy-Equivalent Sampling) For every s-way sampling parameter t there is a single-pivot random-parameter scheme with the same quality of pivots. (formal meaning: same denominator) Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
246. Entropy-Equivalent Sampling Key Idea: Simulate by binary partitioning. One round of 4-way partitioning ... (without sampling) < < < <P2 <P1 c1 c2 <P3 c3 c4 ...corresponds to three binary partitionings. < <P2 c1,2 c3,4 < <P1 c1 c2 < <P3 c3 c4 But how to choose pivots P1, P2, P3? P2 is chosen as median of 3! P1 and P3 uniform! can simulate 4-way partitioning exactly by alternating between median-of-3 and no sampling. same on average: 1 flip a fair coin 2 median-of-3 for heads no sampling for tails random-parameter pivot sampling Theorem (Entropy-Equivalent Sampling) For every s-way sampling parameter t there is a single-pivot random-parameter scheme with the same quality of pivots. (formal meaning: same denominator) Example: t = (1, 1, 1) with T = (3, 1) with prob. 3 5 (1, 1) otherwise Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 19 / 22
247. Finally: The Fair Competition Compare multiway method to b rounds of binary partitioning. b = average number of binary partitioning rounds per element. Consider YBB Quicksort with t = (1, 1, 1) 2 options 1 First around P, then around Q b = 1 + E D2 + D3 2 First around Q, then around P b = 1 + E D1 + D2 b = 1 + 2 3 = 1.6 (in both cases here) but YBB costs 34 21 ≈ 1.619 cmps/element −2.9% 4 3 = 1.3 scans/element −20% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 20 / 22
248. Finally: The Fair Competition Compare multiway method to b rounds of binary partitioning. b = average number of binary partitioning rounds per element. Consider YBB Quicksort with t = (1, 1, 1) 2 options 1 First around P, then around Q b = 1 + E D2 + D3 2 First around Q, then around P b = 1 + E D1 + D2 b = 1 + 2 3 = 1.6 (in both cases here) but YBB costs 34 21 ≈ 1.619 cmps/element −2.9% 4 3 = 1.3 scans/element −20% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 20 / 22
249. Finally: The Fair Competition Compare multiway method to b rounds of binary partitioning. b = average number of binary partitioning rounds per element. Consider YBB Quicksort with t = (1, 1, 1) 2 options 1 First around P, then around Q < <P1 c1 c2,3 < <P2 c2 c3 k g k g b = 1 + E D2 + D3 2 First around Q, then around P b = 1 + E D1 + D2 b = 1 + 2 3 = 1.6 (in both cases here) but YBB costs 34 21 ≈ 1.619 cmps/element −2.9% 4 3 = 1.3 scans/element −20% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 20 / 22
250. Finally: The Fair Competition Compare multiway method to b rounds of binary partitioning. b = average number of binary partitioning rounds per element. Consider YBB Quicksort with t = (1, 1, 1) 2 options 1 First around P, then around Q < <P1 c1 c2,3 < <P2 c2 c3 k g k g b = 1 + E D2 + D3 2 First around Q, then around P < <P2 c1,2 c3 < <P1 c1 c2 k g k g b = 1 + E D1 + D2 b = 1 + 2 3 = 1.6 (in both cases here) but YBB costs 34 21 ≈ 1.619 cmps/element −2.9% 4 3 = 1.3 scans/element −20% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 20 / 22
251. Finally: The Fair Competition Compare multiway method to b rounds of binary partitioning. b = average number of binary partitioning rounds per element. Consider YBB Quicksort with t = (1, 1, 1) 2 options 1 First around P, then around Q < <P1 c1 c2,3 < <P2 c2 c3 k g k g b = 1 + E D2 + D3 2 First around Q, then around P < <P2 c1,2 c3 < <P1 c1 c2 k g k g b = 1 + E D1 + D2 b = 1 + 2 3 = 1.6 (in both cases here) but YBB costs 34 21 ≈ 1.619 cmps/element −2.9% 4 3 = 1.3 scans/element −20% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 20 / 22
252. Finally: The Fair Competition Compare multiway method to b rounds of binary partitioning. b = average number of binary partitioning rounds per element. Consider YBB Quicksort with t = (1, 1, 1) 2 options 1 First around P, then around Q < <P1 c1 c2,3 < <P2 c2 c3 k g k g b = 1 + E D2 + D3 2 First around Q, then around P < <P2 c1,2 c3 < <P1 c1 c2 k g k g b = 1 + E D1 + D2 b = 1 + 2 3 = 1.6 (in both cases here) but YBB costs 34 21 ≈ 1.619 cmps/element −2.9% 4 3 = 1.3 scans/element −20% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 20 / 22
253. Finally: The Fair Competition Compare multiway method to b rounds of binary partitioning. b = average number of binary partitioning rounds per element. Consider YBB Quicksort with t = (1, 1, 1) 2 options 1 First around P, then around Q < <P1 c1 c2,3 < <P2 c2 c3 k g k g b = 1 + E D2 + D3 2 First around Q, then around P < <P2 c1,2 c3 < <P1 c1 c2 k g k g b = 1 + E D1 + D2 b = 1 + 2 3 = 1.6 (in both cases here) but YBB costs 34 21 ≈ 1.619 cmps/element −2.9% 4 3 = 1.3 scans/element −20% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 20 / 22
254. Finally: The Fair Competition Compare multiway method to b rounds of binary partitioning. b = average number of binary partitioning rounds per element. Consider YBB Quicksort with t = (1, 1, 1) 2 options 1 First around P, then around Q < <P1 c1 c2,3 < <P2 c2 c3 k g k g b = 1 + E D2 + D3 2 First around Q, then around P < <P2 c1,2 c3 < <P1 c1 c2 k g k g b = 1 + E D1 + D2 b = 1 + 2 3 = 1.6 (in both cases here) but YBB costs 34 21 ≈ 1.619 cmps/element −2.9% 4 3 = 1.3 scans/element −20% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 20 / 22
255. Finally: The Fair Competition Compare multiway method to b rounds of binary partitioning. b = average number of binary partitioning rounds per element. Consider YBB Quicksort with t = (1, 1, 1) 2 options 1 First around P, then around Q < <P1 c1 c2,3 < <P2 c2 c3 k g k g b = 1 + E D2 + D3 2 First around Q, then around P < <P2 c1,2 c3 < <P1 c1 c2 k g k g b = 1 + E D1 + D2 b = 1 + 2 3 = 1.6 (in both cases here) but YBB costs 34 21 ≈ 1.619 cmps/element −2.9% 4 3 = 1.3 scans/element −20% But: scanned-element-optimal: t = (0, 1, 2) 1.34... vs. 1.40... Option 2 strictly better: b = 1.5 YBB costs 34 21 ≈ 1.619 cmps/element +7.9% 7 6 = 1.16 scans/element −22.2% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 20 / 22
256. Finally: The Fair Competition Compare multiway method to b rounds of binary partitioning. b = average number of binary partitioning rounds per element. Consider YBB Quicksort with t = (1, 1, 1) 2 options 1 First around P, then around Q < <P1 c1 c2,3 < <P2 c2 c3 k g k g b = 1 + E D2 + D3 2 First around Q, then around P < <P2 c1,2 c3 < <P1 c1 c2 k g k g b = 1 + E D1 + D2 b = 1 + 2 3 = 1.6 (in both cases here) but YBB costs 34 21 ≈ 1.619 cmps/element −2.9% 4 3 = 1.3 scans/element −20% But: scanned-element-optimal: t = (0, 1, 2) Option 2 strictly better: 1 b = 1.83 b = 1.5 YBB costs 34 21 ≈ 1.619 cmps/element +7.9% 7 6 = 1.16 scans/element −22.2% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 20 / 22
257. Finally: The Fair Competition Compare multiway method to b rounds of binary partitioning. b = average number of binary partitioning rounds per element. Consider YBB Quicksort with t = (1, 1, 1) 2 options 1 First around P, then around Q < <P1 c1 c2,3 < <P2 c2 c3 k g k g b = 1 + E D2 + D3 2 First around Q, then around P < <P2 c1,2 c3 < <P1 c1 c2 k g k g b = 1 + E D1 + D2 b = 1 + 2 3 = 1.6 (in both cases here) but YBB costs 34 21 ≈ 1.619 cmps/element −2.9% 4 3 = 1.3 scans/element −20% But: scanned-element-optimal: t = (0, 1, 2) Option 2 strictly better: b = 1.5 YBB costs 34 21 ≈ 1.619 cmps/element +7.9% 7 6 = 1.16 scans/element −22.2% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 20 / 22
258. Finally: The Fair Competition Compare multiway method to b rounds of binary partitioning. b = average number of binary partitioning rounds per element. Consider YBB Quicksort with t = (1, 1, 1) 2 options 1 First around P, then around Q < <P1 c1 c2,3 < <P2 c2 c3 k g k g b = 1 + E D2 + D3 2 First around Q, then around P < <P2 c1,2 c3 < <P1 c1 c2 k g k g b = 1 + E D1 + D2 b = 1 + 2 3 = 1.6 (in both cases here) but YBB costs 34 21 ≈ 1.619 cmps/element −2.9% 4 3 = 1.3 scans/element −20% But: scanned-element-optimal: t = (0, 1, 2) Option 2 strictly better: b = 1.5 YBB costs 34 21 ≈ 1.619 cmps/element +7.9% 7 6 = 1.16 scans/element −22.2% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 20 / 22
259. Finally: The Fair Competition Compare multiway method to b rounds of binary partitioning. b = average number of binary partitioning rounds per element. Consider YBB Quicksort with t = (1, 1, 1) 2 options 1 First around P, then around Q < <P1 c1 c2,3 < <P2 c2 c3 k g k g b = 1 + E D2 + D3 2 First around Q, then around P < <P2 c1,2 c3 < <P1 c1 c2 k g k g b = 1 + E D1 + D2 b = 1 + 2 3 = 1.6 (in both cases here) but YBB costs 34 21 ≈ 1.619 cmps/element −2.9% 4 3 = 1.3 scans/element −20% But: scanned-element-optimal: t = (0, 1, 2) Option 2 strictly better: b = 1.5 YBB costs 34 21 ≈ 1.619 cmps/element +7.9% 7 6 = 1.16 scans/element −22.2% Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 20 / 22
260. Finally: The Fair Competition Compare multiway method to b rounds of binary partitioning. b = average number of binary partitioning rounds per element. Consider YBB Quicksort with t = (1, 1, 1) 2 options 1 First around P, then around Q < <P1 c1 c2,3 < <P2 c2 c3 k g k g b = 1 + E D2 + D3 2 First around Q, then around P < <P2 c1,2 c3 < <P1 c1 c2 k g k g b = 1 + E D1 + D2 b = 1 + 2 3 = 1.6 (in both cases here) but YBB costs 34 21 ≈ 1.619 cmps/element −2.9% 4 3 = 1.3 scans/element −20% But: scanned-element-optimal: t = (0, 1, 2) Option 2 strictly better: b = 1.5 YBB costs 34 21 ≈ 1.619 cmps/element +7.9% 7 6 = 1.16 scans/element −22.2% General Observation Comparisons: hardly any savings if k grows, often even costly Scanned Elements: significant savings large k helps, need asymmetric t Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 20 / 22
261. Conclusion You have seen: 1 tricky asymmetries in YBB Quicksort saves a few comparisons but: savings vanish with pivot sampling 2 scanned elements simple cost model for memory transfer significant savings possible with multiway partitioning 3 entropy-equivalent sampling separate effects: better pivots vs. partitioning method fair comparison Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 21 / 22
262. Conclusion You have seen: 1 tricky asymmetries in YBB Quicksort saves a few comparisons but: savings vanish with pivot sampling 2 scanned elements simple cost model for memory transfer significant savings possible with multiway partitioning 3 entropy-equivalent sampling separate effects: better pivots vs. partitioning method fair comparison Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 21 / 22
263. Conclusion You have seen: 1 tricky asymmetries in YBB Quicksort saves a few comparisons but: savings vanish with pivot sampling 2 scanned elements simple cost model for memory transfer significant savings possible with multiway partitioning 3 entropy-equivalent sampling separate effects: better pivots vs. partitioning method fair comparison Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 21 / 22
264. Conclusion You have seen: 1 tricky asymmetries in YBB Quicksort saves a few comparisons but: savings vanish with pivot sampling 2 scanned elements simple cost model for memory transfer significant savings possible with multiway partitioning 3 entropy-equivalent sampling separate effects: better pivots vs. partitioning method fair comparison Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 21 / 22
265. Conclusion You have seen: 1 tricky asymmetries in YBB Quicksort saves a few comparisons but: savings vanish with pivot sampling 2 scanned elements simple cost model for memory transfer significant savings possible with multiway partitioning 3 entropy-equivalent sampling separate effects: better pivots vs. partitioning method fair comparison Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 21 / 22
266. Conclusion You have seen: 1 tricky asymmetries in YBB Quicksort saves a few comparisons but: savings vanish with pivot sampling 2 scanned elements simple cost model for memory transfer significant savings possible with multiway partitioning 3 entropy-equivalent sampling separate effects: better pivots vs. partitioning method fair comparison Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 21 / 22
267. Conclusion You have seen: 1 tricky asymmetries in YBB Quicksort saves a few comparisons but: savings vanish with pivot sampling 2 scanned elements simple cost model for memory transfer significant savings possible with multiway partitioning genuine potential of multiway partitioning! 3 entropy-equivalent sampling separate effects: better pivots vs. partitioning method fair comparison Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 21 / 22
268. Conclusion You have seen: 1 tricky asymmetries in YBB Quicksort saves a few comparisons but: savings vanish with pivot sampling 2 scanned elements simple cost model for memory transfer significant savings possible with multiway partitioning genuine potential of multiway partitioning! 3 entropy-equivalent sampling separate effects: better pivots vs. partitioning method fair comparison Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 21 / 22
269. Conclusion You have seen: 1 tricky asymmetries in YBB Quicksort saves a few comparisons but: savings vanish with pivot sampling 2 scanned elements simple cost model for memory transfer significant savings possible with multiway partitioning genuine potential of multiway partitioning! 3 entropy-equivalent sampling separate effects: better pivots vs. partitioning method fair comparison Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 21 / 22
270. Conclusion You have seen: 1 tricky asymmetries in YBB Quicksort saves a few comparisons but: savings vanish with pivot sampling 2 scanned elements simple cost model for memory transfer significant savings possible with multiway partitioning genuine potential of multiway partitioning! 3 entropy-equivalent sampling separate effects: better pivots vs. partitioning method fair comparison Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 21 / 22
271. Conclusion You have seen: 1 tricky asymmetries in YBB Quicksort saves a few comparisons but: savings vanish with pivot sampling 2 scanned elements simple cost model for memory transfer significant savings possible with multiway partitioning genuine potential of multiway partitioning! 3 entropy-equivalent sampling separate effects: better pivots vs. partitioning method fair comparison You have not seen: Branch mispredictions 1 taken 2 taken 3 not t. 4 not t. taken not t. not t. not t. not t. taken taken taken Treatment of equal keys 4 2 1 3 3 5 4 4 3 5 2 2 1 2 4 5 4 4 5 3 3 3 5 5 4 4 4 2 1 2 5 5 4 2 1 3 3 5 4 4 3 5 2 3 4 5 5 2 1 2 Intriguing interplay of parameters Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 21 / 22
272. Conclusion You have seen: 1 tricky asymmetries in YBB Quicksort saves a few comparisons but: savings vanish with pivot sampling 2 scanned elements simple cost model for memory transfer significant savings possible with multiway partitioning genuine potential of multiway partitioning! 3 entropy-equivalent sampling separate effects: better pivots vs. partitioning method fair comparison You have not seen: Branch mispredictions 1 taken 2 taken 3 not t. 4 not t. taken not t. not t. not t. not t. taken taken taken Treatment of equal keys 4 2 1 3 3 5 4 4 3 5 2 2 1 2 4 5 4 4 5 3 3 3 5 5 4 4 4 2 1 2 5 5 4 2 1 3 3 5 4 4 3 5 2 3 4 5 5 2 1 2 Intriguing interplay of parameters Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 21 / 22
273. Conclusion You have seen: 1 tricky asymmetries in YBB Quicksort saves a few comparisons but: savings vanish with pivot sampling 2 scanned elements simple cost model for memory transfer significant savings possible with multiway partitioning genuine potential of multiway partitioning! 3 entropy-equivalent sampling separate effects: better pivots vs. partitioning method fair comparison You have not seen: Branch mispredictions 1 taken 2 taken 3 not t. 4 not t. taken not t. not t. not t. not t. taken taken taken Treatment of equal keys 4 2 1 3 3 5 4 4 3 5 2 2 1 2 4 5 4 4 5 3 3 3 5 5 4 4 4 2 1 2 5 5 4 2 1 3 3 5 4 4 3 5 2 3 4 5 5 2 1 2 Intriguing interplay of parameters Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 21 / 22
274. Conclusion You have seen: 1 tricky asymmetries in YBB Quicksort saves a few comparisons but: savings vanish with pivot sampling 2 scanned elements simple cost model for memory transfer significant savings possible with multiway partitioning genuine potential of multiway partitioning! 3 entropy-equivalent sampling separate effects: better pivots vs. partitioning method fair comparison You have not seen: Branch mispredictions 1 taken 2 taken 3 not t. 4 not t. taken not t. not t. not t. not t. taken taken taken Treatment of equal keys 4 2 1 3 3 5 4 4 3 5 2 2 1 2 4 5 4 4 5 3 3 3 5 5 4 4 4 2 1 2 5 5 4 2 1 3 3 5 4 4 3 5 2 3 4 5 5 2 1 2 Intriguing interplay of parameters Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 21 / 22
275. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 22 / 22
276. Icons made by Freepik, Gregor Cresnar and Madebyoliver from www.flaticon.com. Mousetrap Image from bobbleheaddad.com Top Trumps Card from winningmoves.co.uk. Sebastian Wild Dual-Pivot Quicksort and Beyond 2016-09-06 23 / 22