search!) clean data (remove dups, get canonical form of things) to present data neatly for users as building block in algorithms (database join, sweepline, ...) ... built-in functions in Python: my_list.sort() and sorted(my_list) key parameter to specify sorting criterion prefer pairwise comparator function? ⇝ functools.cmp_to_key Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 1 / 19
search!) clean data (remove dups, get canonical form of things) to present data neatly for users as building block in algorithms (database join, sweepline, ...) ... built-in functions in Python: my_list.sort() and sorted(my_list) key parameter to specify sorting criterion prefer pairwise comparator function? ⇝ functools.cmp_to_key Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 1 / 19
not stable Mergesort is generally (quite) fast and stable, but not in place stable and in place is tricky (possible, but relatively slow) Python has lots of objects and pointers anyways ... “in-place” property least painful to sacrifice ⇝ Mergesort! Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 4 / 19
not stable Mergesort is generally (quite) fast and stable, but not in place stable and in place is tricky (possible, but relatively slow) Python has lots of objects and pointers anyways ... “in-place” property least painful to sacrifice ⇝ Mergesort! Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 4 / 19
not stable Mergesort is generally (quite) fast and stable, but not in place stable and in place is tricky (possible, but relatively slow) Python has lots of objects and pointers anyways ... “in-place” property least painful to sacrifice ⇝ Mergesort! Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 4 / 19
not stable Mergesort is generally (quite) fast and stable, but not in place stable and in place is tricky (possible, but relatively slow) “Pick any two!” stable fast, few cmps in place ≈ honest smart investment banker Python has lots of objects and pointers anyways ... “in-place” property least painful to sacrifice ⇝ Mergesort! Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 4 / 19
not stable Mergesort is generally (quite) fast and stable, but not in place stable and in place is tricky (possible, but relatively slow) “Pick any two!” stable fast, few cmps in place ≈ honest smart investment banker Python has lots of objects and pointers anyways ... “in-place” property least painful to sacrifice ⇝ Mergesort! Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 4 / 19
increasing or (strictly) decreasing range 2 galloping merges use exponential searches to find position in other run 3 minimum run lengths with binary insertion sort choose 32 ⩽ minrun ⩽ 64, so that ⌈ n minrun ⌉ is 2k or slightly smaller fill runs to minrun elements 4 merge policy decides when to merge which runs 5 keeping runs on a fixed-size runstack Tim Peters et al.: listsort.txt, CPython sources Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 6 / 19
0; runs = [] 3 while i < len(lst): 4 j = extend_run(lst, i) 5 runs.append((i,j-i)); i = j 6 while Rule A/B/C applicable 7 merge X,Y resp. Y,Z 8 while len(runs) > 1: 9 merge Y,Z Z Y X . . . top runs Rule A: Z > X ⇝ merge(X, Y) Z Y X . . . Z X+Y . . . Rule B: Z ≥ Y ⇝ merge(Y, Z) ¬ A Z Y . . . Y+Z . . . Rule C: Y + Z ≥ X ⇝ merge(Y, Z) ¬ A, ¬ B Z Y X Z . . . Y+Z X . . . extend_run detects next run & boosts to minrun if necessary Goal: runs on stack grow like Fibonacci numbers Invariant: ∀j : runs[j] ⩾ runs[j + 1] + runs[j + 2] ⇝ max stack height ≈ logφ (n) Why exactly these rules? Tim Peters: “first thing I tried that ‘worked well (a) small runs stack, (b) balanced on equal runs, (c) O(n log n) worst case* ’” full code: tiny.cc/timsort Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 7 / 19
0; runs = [] 3 while i < len(lst): 4 j = extend_run(lst, i) 5 runs.append((i,j-i)); i = j 6 while Rule A/B/C applicable 7 merge X,Y resp. Y,Z 8 while len(runs) > 1: 9 merge Y,Z Z Y X . . . top runs Rule A: Z > X ⇝ merge(X, Y) Z Y X . . . Z X+Y . . . Rule B: Z ≥ Y ⇝ merge(Y, Z) ¬ A Z Y . . . Y+Z . . . Rule C: Y + Z ≥ X ⇝ merge(Y, Z) ¬ A, ¬ B Z Y X Z . . . Y+Z X . . . extend_run detects next run & boosts to minrun if necessary Goal: runs on stack grow like Fibonacci numbers Invariant: ∀j : runs[j] ⩾ runs[j + 1] + runs[j + 2] ⇝ max stack height ≈ logφ (n) Why exactly these rules? Tim Peters: “first thing I tried that ‘worked well (a) small runs stack, (b) balanced on equal runs, (c) O(n log n) worst case* ’” full code: tiny.cc/timsort Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 7 / 19
0; runs = [] 3 while i < len(lst): 4 j = extend_run(lst, i) 5 runs.append((i,j-i)); i = j 6 while Rule A/B/C applicable 7 merge X,Y resp. Y,Z 8 while len(runs) > 1: 9 merge Y,Z Z Y X . . . top runs Rule A: Z > X ⇝ merge(X, Y) Z Y X . . . Z X+Y . . . Rule B: Z ≥ Y ⇝ merge(Y, Z) ¬ A Z Y . . . Y+Z . . . Rule C: Y + Z ≥ X ⇝ merge(Y, Z) ¬ A, ¬ B Z Y X Z . . . Y+Z X . . . extend_run detects next run & boosts to minrun if necessary Goal: runs on stack grow like Fibonacci numbers Invariant: ∀j : runs[j] ⩾ runs[j + 1] + runs[j + 2] ⇝ max stack height ≈ logφ (n) Why exactly these rules? Tim Peters: “first thing I tried that ‘worked well (a) small runs stack, (b) balanced on equal runs, (c) O(n log n) worst case* ’” full code: tiny.cc/timsort Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 7 / 19
0; runs = [] 3 while i < len(lst): 4 j = extend_run(lst, i) 5 runs.append((i,j-i)); i = j 6 while Rule A/B/C applicable 7 merge X,Y resp. Y,Z 8 while len(runs) > 1: 9 merge Y,Z Z Y X . . . top runs Rule A: Z > X ⇝ merge(X, Y) Z Y X . . . Z X+Y . . . Rule B: Z ≥ Y ⇝ merge(Y, Z) ¬ A Z Y . . . Y+Z . . . Rule C: Y + Z ≥ X ⇝ merge(Y, Z) ¬ A, ¬ B Z Y X Z . . . Y+Z X . . . extend_run detects next run & boosts to minrun if necessary Goal: runs on stack grow like Fibonacci numbers Invariant: ∀j : runs[j] ⩾ runs[j + 1] + runs[j + 2] ⇝ max stack height ≈ logφ (n) Why exactly these rules? Tim Peters: “first thing I tried that ‘worked well (a) small runs stack, (b) balanced on equal runs, (c) O(n log n) worst case* ’” full code: tiny.cc/timsort Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 7 / 19
0; runs = [] 3 while i < len(lst): 4 j = extend_run(lst, i) 5 runs.append((i,j-i)); i = j 6 while Rule A/B/C applicable 7 merge X,Y resp. Y,Z 8 while len(runs) > 1: 9 merge Y,Z Z Y X . . . top runs Rule A: Z > X ⇝ merge(X, Y) Z Y X . . . Z X+Y . . . Rule B: Z ≥ Y ⇝ merge(Y, Z) ¬ A Z Y . . . Y+Z . . . Rule C: Y + Z ≥ X ⇝ merge(Y, Z) ¬ A, ¬ B Z Y X Z . . . Y+Z X . . . extend_run detects next run & boosts to minrun if necessary Goal: runs on stack grow like Fibonacci numbers Invariant: ∀j : runs[j] ⩾ runs[j + 1] + runs[j + 2] ⇝ max stack height ≈ logφ (n) Why exactly these rules? Tim Peters: “first thing I tried that ‘worked well (a) small runs stack, (b) balanced on equal runs, (c) O(n log n) worst case* ’” full code: tiny.cc/timsort Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 7 / 19
Fibonacci: Invariant: ∀j = 0, . . . , len(runs) − 3 : runs[j] ⩾ runs[j + 1] + runs[j + 2] not true(!) for naughty pattern of run lengths KeY project for formal verification in Java de Gouw, de Boer, Bubel, Hähnle, Rot, Steinhöfel: Verifying OpenJDK’s Sort Method for Generic Collections, J Autom Reasoning 2019 In Java: Arrays.sort(Object[]) could throw ArrayIndexOutOfBoundException for specific input of size 67,108,864 Timsort in Java since 2009, but issue never reported? first (incorrectly!) patched in 2013, then a second time in 2015 ... for CPython: patched in 2015 mostly a theoretical issue (needs ⩾ 249 elements) Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 8 / 19
0; runs = [] 3 while i < len(lst): 4 j = extend_run(lst, i) 5 runs.apppend((i,j)); i = j 6 while Rule A/B/C/D applicable 7 merge corresponding runs 8 while len(runs) > 1: 9 merge topmost 2 runs Z Y X W . . . top runs Rule A: Z > X ⇝ merge(X, Y) Z Y X . . . Z X+Y . . . Rule B: Z ≥ Y ⇝ merge(Y, Z) ¬ A Z Y . . . Y+Z . . . Rule C: Y + Z ≥ X ⇝ merge(Y, Z) ¬ A, ¬ B Z Y X Z . . . Y+Z X . . . Rule D: X + Y ≥ W ⇝ merge(Y, Z) ¬ A, ¬ B, ¬ C Z Y X W Y . . . Y+Z X W . . . Need to add a Rule D ⇝ Invariant: ∀j = 0, . . . , len(runs) − 3 : runs[j] ⩾ runs[j + 1] + runs[j + 2] ✓ running time indeed O(n log n) ...very complicated to prove Auger, Jugé, Nicaud, Pivoteau: On the Worst-Case Complexity of TimSort, ESA 2018 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 9 / 19
0; runs = [] 3 while i < len(lst): 4 j = extend_run(lst, i) 5 runs.apppend((i,j)); i = j 6 while Rule A/B/C/D applicable 7 merge corresponding runs 8 while len(runs) > 1: 9 merge topmost 2 runs Z Y X W . . . top runs Rule A: Z > X ⇝ merge(X, Y) Z Y X . . . Z X+Y . . . Rule B: Z ≥ Y ⇝ merge(Y, Z) ¬ A Z Y . . . Y+Z . . . Rule C: Y + Z ≥ X ⇝ merge(Y, Z) ¬ A, ¬ B Z Y X Z . . . Y+Z X . . . Rule D: X + Y ≥ W ⇝ merge(Y, Z) ¬ A, ¬ B, ¬ C Z Y X W Y . . . Y+Z X W . . . Need to add a Rule D ⇝ Invariant: ∀j = 0, . . . , len(runs) − 3 : runs[j] ⩾ runs[j + 1] + runs[j + 2] ✓ running time indeed O(n log n) ...very complicated to prove Auger, Jugé, Nicaud, Pivoteau: On the Worst-Case Complexity of TimSort, ESA 2018 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 9 / 19
0; runs = [] 3 while i < len(lst): 4 j = extend_run(lst, i) 5 runs.apppend((i,j)); i = j 6 while Rule A/B/C/D applicable 7 merge corresponding runs 8 while len(runs) > 1: 9 merge topmost 2 runs Z Y X W . . . top runs Rule A: Z > X ⇝ merge(X, Y) Z Y X . . . Z X+Y . . . Rule B: Z ≥ Y ⇝ merge(Y, Z) ¬ A Z Y . . . Y+Z . . . Rule C: Y + Z ≥ X ⇝ merge(Y, Z) ¬ A, ¬ B Z Y X Z . . . Y+Z X . . . Rule D: X + Y ≥ W ⇝ merge(Y, Z) ¬ A, ¬ B, ¬ C Z Y X W Y . . . Y+Z X W . . . Need to add a Rule D ⇝ Invariant: ∀j = 0, . . . , len(runs) − 3 : runs[j] ⩾ runs[j + 1] + runs[j + 2] ✓ running time indeed O(n log n) ...very complicated to prove Auger, Jugé, Nicaud, Pivoteau: On the Worst-Case Complexity of TimSort, ESA 2018 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 9 / 19
0; runs = [] 3 while i < len(lst): 4 j = extend_run(lst, i) 5 runs.apppend((i,j)); i = j 6 while Rule A/B/C/D applicable 7 merge corresponding runs 8 while len(runs) > 1: 9 merge topmost 2 runs Z Y X W . . . top runs Rule A: Z > X ⇝ merge(X, Y) Z Y X . . . Z X+Y . . . Rule B: Z ≥ Y ⇝ merge(Y, Z) ¬ A Z Y . . . Y+Z . . . Rule C: Y + Z ≥ X ⇝ merge(Y, Z) ¬ A, ¬ B Z Y X Z . . . Y+Z X . . . Rule D: X + Y ≥ W ⇝ merge(Y, Z) ¬ A, ¬ B, ¬ C Z Y X W Y . . . Y+Z X W . . . Need to add a Rule D ⇝ Invariant: ∀j = 0, . . . , len(runs) − 3 : runs[j] ⩾ runs[j + 1] + runs[j + 2] ✓ running time indeed O(n log n) ...very complicated to prove Auger, Jugé, Nicaud, Pivoteau: On the Worst-Case Complexity of TimSort, ESA 2018 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 9 / 19
0; runs = [] 3 while i < len(lst): 4 j = extend_run(lst, i) 5 runs.apppend((i,j)); i = j 6 while Rule A/B/C/D applicable 7 merge corresponding runs 8 while len(runs) > 1: 9 merge topmost 2 runs Z Y X W . . . top runs Rule A: Z > X ⇝ merge(X, Y) Z Y X . . . Z X+Y . . . Rule B: Z ≥ Y ⇝ merge(Y, Z) ¬ A Z Y . . . Y+Z . . . Rule C: Y + Z ≥ X ⇝ merge(Y, Z) ¬ A, ¬ B Z Y X Z . . . Y+Z X . . . Rule D: X + Y ≥ W ⇝ merge(Y, Z) ¬ A, ¬ B, ¬ C Z Y X W Y . . . Y+Z X W . . . Need to add a Rule D ⇝ Invariant: ∀j = 0, . . . , len(runs) − 3 : runs[j] ⩾ runs[j + 1] + runs[j + 2] ✓ running time indeed O(n log n) ...very complicated to prove Auger, Jugé, Nicaud, Pivoteau: On the Worst-Case Complexity of TimSort, ESA 2018 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 9 / 19
does stupid things on certain inputs: intuitive problem: regularly very unbalanced merges Buss, Knop: Strategies for Stable Merge Sorting, SODA 2019 can do much better (merge cost 321 vs. 371) As n increases, 50% higher merge cost than standard mergesort Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 10 / 19
code tually two steps: 1 Find runs in input. 2 Merge them in some order determined by merge policy . Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 11 / 19
code tually two steps: 1 Find runs in input. 2 Merge them in some order determined by merge policy . Here: only binary merges ⇝ 2 becomes: merge 2 runs, repeat until single run only stable sorts ⇝ merge 2 adjacent runs Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 11 / 19
code tually two steps: 1 Find runs in input. 2 Merge them in some order determined by merge policy . Here: only binary merges ⇝ 2 becomes: merge 2 runs, repeat until single run only stable sorts ⇝ merge 2 adjacent runs Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 11 / 19
code tually two steps: 1 Find runs in input. 2 Merge them in some order determined by merge policy . Here: only binary merges ⇝ 2 becomes: merge 2 runs, repeat until single run only stable sorts ⇝ merge 2 adjacent runs Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 11 / 19
code tually two steps: 1 Find runs in input. 2 Merge them in some order determined by merge policy . Here: only binary merges ⇝ 2 becomes: merge 2 runs, repeat until single run only stable sorts ⇝ merge 2 adjacent runs ⇝ Merge order = merge tree: ⇝ Merge policy = algorithm to choose merge tree Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 11 / 19
code tually two steps: 1 Find runs in input. 2 Merge them in some order determined by merge policy . Here: only binary merges ⇝ 2 becomes: merge 2 runs, repeat until single run only stable sorts ⇝ merge 2 adjacent runs ⇝ Merge order = merge tree: ⇝ Merge policy = algorithm to choose merge tree Merge costs cost of merge := size of output ≈ memory transfers ⩾ #cmps total cost = total area of Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 11 / 19
2 6 Merge cost = total area of = total length of paths to all array entries = weighted external path w leaf weight(w) · depth(w) length Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 12 / 19
2 6 Merge cost = total area of = total length of paths to all array entries = weighted external path w leaf weight(w) · depth(w) length ⇝ optimal merge tree = optimal BST for leaf weights L run lengths 1 , . . . , Lr Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 12 / 19
2 6 Merge cost = total area of = total length of paths to all array entries = weighted external path w leaf weight(w) · depth(w) length ⇝ optimal merge tree = optimal BST for leaf weights L run lengths 1 , . . . , Lr ⇝ merge cost ⩾ Hn with H = r i=1 Li n log2 n Li Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 12 / 19
2 6 Merge cost = total area of = total length of paths to all array entries = weighted external path w leaf weight(w) · depth(w) length ⇝ optimal merge tree = optimal BST for leaf weights L run lengths 1 , . . . , Lr ⇝ merge cost ⩾ Hn with H = r i=1 Li n log2 n Li How to compute good merge trees? nearly-optimal ...70s are calling BST merge simple (greedy) linear-time methods! almost optimal (⩽ H + 2) ⇝ Powersort based on the bisection method Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to perfect binary tree Find run boundary closest to middle Recurse on both sides But: Can’t use recursion! Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 12 / 19
2 6 Merge cost = total area of = total length of paths to all array entries = weighted external path w leaf weight(w) · depth(w) length ⇝ optimal merge tree = optimal BST for leaf weights L run lengths 1 , . . . , Lr ⇝ merge cost ⩾ Hn with H = r i=1 Li n log2 n Li How to compute good merge trees? nearly-optimal ...70s are calling BST merge simple (greedy) linear-time methods! almost optimal (⩽ H + 2) ⇝ Powersort based on the bisection method Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to perfect binary tree Find run boundary closest to middle Recurse on both sides But: Can’t use recursion! Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 12 / 19
2 6 Merge cost = total area of = total length of paths to all array entries = weighted external path w leaf weight(w) · depth(w) length ⇝ optimal merge tree = optimal BST for leaf weights L run lengths 1 , . . . , Lr ⇝ merge cost ⩾ Hn with H = r i=1 Li n log2 n Li How to compute good merge trees? nearly-optimal ...70s are calling BST merge simple (greedy) linear-time methods! almost optimal (⩽ H + 2) ⇝ Powersort based on the bisection method Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to perfect binary tree Find run boundary closest to middle Recurse on both sides But: Can’t use recursion! Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 12 / 19
2 6 Merge cost = total area of = total length of paths to all array entries = weighted external path w leaf weight(w) · depth(w) length ⇝ optimal merge tree = optimal BST for leaf weights L run lengths 1 , . . . , Lr ⇝ merge cost ⩾ Hn with H = r i=1 Li n log2 n Li How to compute good merge trees? nearly-optimal ...70s are calling BST merge simple (greedy) linear-time methods! almost optimal (⩽ H + 2) ⇝ Powersort based on the bisection method Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to perfect binary tree Find run boundary closest to middle Recurse on both sides But: Can’t use recursion! Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 12 / 19
2 6 Merge cost = total area of = total length of paths to all array entries = weighted external path w leaf weight(w) · depth(w) length ⇝ optimal merge tree = optimal BST for leaf weights L run lengths 1 , . . . , Lr ⇝ merge cost ⩾ Hn with H = r i=1 Li n log2 n Li How to compute good merge trees? nearly-optimal ...70s are calling BST merge simple (greedy) linear-time methods! almost optimal (⩽ H + 2) ⇝ Powersort based on the bisection method Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to perfect binary tree Find run boundary closest to middle Recurse on both sides But: Can’t use recursion! Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 12 / 19
2 6 Merge cost = total area of = total length of paths to all array entries = weighted external path w leaf weight(w) · depth(w) length ⇝ optimal merge tree = optimal BST for leaf weights L run lengths 1 , . . . , Lr ⇝ merge cost ⩾ Hn with H = r i=1 Li n log2 n Li How to compute good merge trees? nearly-optimal ...70s are calling BST merge simple (greedy) linear-time methods! almost optimal (⩽ H + 2) ⇝ Powersort based on the bisection method Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to perfect binary tree Find run boundary closest to middle Recurse on both sides But: Can’t use recursion! Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 12 / 19
runs = normalized midpoint interval power = min ℓ s.t. contains c · 2−ℓ Bi 0 1 2−p ai bi ℓi−1 ℓi Pi ⩽ p 1 def power(run1, run2, n): 2 i1, n1 = run1 3 i2, n2 = run2 4 a = (i1 + n1/2) / n 5 b = (i2 + n2/2) / n 6 l = 0 7 while math.floor(a * 2**l) == \ 8 math.floor(b * 2**l): 9 l += 1 10 return l More efficient implementation possible (avoid multiplication / division in loop) Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 16 / 19
0-5% fewer comparisons; occasionally 20–30%. Data (One can contrive inputs where Powersort does worse; seems inevitable) 2 No running time regressions: never measurably slower in actual running time Data 3 Sometimes substantially faster (20–40%) Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 17 / 19
Python ... In other contexts, comparisons can be much cheaper ⇝ need to economize on memory transfers* ⇝ can profit from multiway merging (instead of 2 runs at a time) ⇝ Easy to do with Powersort while keeping adaptivity! Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 18 / 19
Python ... = now using Powersort merge policy In other contexts, comparisons can be much cheaper ⇝ need to economize on memory transfers* ⇝ can profit from multiway merging (instead of 2 runs at a time) ⇝ Easy to do with Powersort while keeping adaptivity! Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 18 / 19
Python ... = now using Powersort merge policy In other contexts, comparisons can be much cheaper ⇝ need to economize on memory transfers* ⇝ can profit from multiway merging (instead of 2 runs at a time) ⇝ Easy to do with Powersort while keeping adaptivity! Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 18 / 19
Python ... = now using Powersort merge policy In other contexts, comparisons can be much cheaper ⇝ need to economize on memory transfers* ⇝ can profit from multiway merging (instead of 2 runs at a time) * (My PhD was on how this affects Quicksort) Wild: Dual-Pivot Quicksort and Beyond: Analysis of Multiway Partitioning and Its Practical Potential, PhD thesis 2016 ⇝ Easy to do with Powersort while keeping adaptivity! Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 18 / 19
Python ... = now using Powersort merge policy In other contexts, comparisons can be much cheaper ⇝ need to economize on memory transfers* ⇝ can profit from multiway merging (instead of 2 runs at a time) * (My PhD was on how this affects Quicksort) Wild: Dual-Pivot Quicksort and Beyond: Analysis of Multiway Partitioning and Its Practical Potential, PhD thesis 2016 ⇝ Easy to do with Powersort while keeping adaptivity! Cawley Gelling, Nebel, Smith, Wild: Multiway Powersort, ALENEX 2023 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 18 / 19
original merge policy wasn’t ideal complicated correctness proof / analysis blind spots in performance Powersort fixes this! K And they lived merrily every after. k Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 19 / 19
original merge policy wasn’t ideal complicated correctness proof / analysis blind spots in performance Powersort fixes this! K And they lived merrily every after. k Goals 1 Powersort in other libraries using Timsort? numpy & pandas OpenJDK Android Java runtime V8 JavaScript engine GNU STL std::stable_sort Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 19 / 19
original merge policy wasn’t ideal complicated correctness proof / analysis blind spots in performance Powersort fixes this! K And they lived merrily every after. k Goals 1 Powersort in other libraries using Timsort? numpy & pandas OpenJDK Android Java runtime V8 JavaScript engine GNU STL std::stable_sort 2 How much does adaptive sorting help? What are typical inputs like in difference applications? Is sorting used at all? Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 19 / 19
original merge policy wasn’t ideal complicated correctness proof / analysis blind spots in performance Powersort fixes this! K And they lived merrily every after. k Goals 1 Powersort in other libraries using Timsort? numpy & pandas OpenJDK Android Java runtime V8 JavaScript engine GNU STL std::stable_sort 2 How much does adaptive sorting help? What are typical inputs like in difference applications? Is sorting used at all? Please help me with your data I only care about relative ordering ! Instructions to contribute: tiny.cc/sort-lake-city Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 19 / 19
Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to a perfectly balanced binary tree Pretend array is interval [0, 1] Find run boundaries closest to middle Recurse on both sides Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 21 / 19
Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to a perfectly balanced binary tree Pretend array is interval [0, 1] Find run boundaries closest to middle Recurse on both sides Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 21 / 19
Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to a perfectly balanced binary tree Pretend array is interval [0, 1] Find run boundaries closest to middle Recurse on both sides 1⁄ 2 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 21 / 19
Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to a perfectly balanced binary tree Pretend array is interval [0, 1] Find run boundaries closest to middle Recurse on both sides 1⁄ 2 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 21 / 19
Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to a perfectly balanced binary tree Pretend array is interval [0, 1] Find run boundaries closest to middle Recurse on both sides 1⁄ 2 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 21 / 19
Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to a perfectly balanced binary tree Pretend array is interval [0, 1] Find run boundaries closest to middle Recurse on both sides 1⁄ 2 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 21 / 19
Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to a perfectly balanced binary tree Pretend array is interval [0, 1] Find run boundaries closest to middle Recurse on both sides 1⁄ 2 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 21 / 19
Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to a perfectly balanced binary tree Pretend array is interval [0, 1] Find run boundaries closest to middle Recurse on both sides 1⁄ 2 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 21 / 19
Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to a perfectly balanced binary tree Pretend array is interval [0, 1] Find run boundaries closest to middle Recurse on both sides 1⁄ 2 1⁄ 2 1⁄ 4 3⁄ 4 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 21 / 19
Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to a perfectly balanced binary tree Pretend array is interval [0, 1] Find run boundaries closest to middle Recurse on both sides 1⁄ 2 1⁄ 2 1⁄ 4 3⁄ 4 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 21 / 19
Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to a perfectly balanced binary tree Pretend array is interval [0, 1] Find run boundaries closest to middle Recurse on both sides 1⁄ 2 1⁄ 2 1⁄ 4 3⁄ 4 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 21 / 19
Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to a perfectly balanced binary tree Pretend array is interval [0, 1] Find run boundaries closest to middle Recurse on both sides 1⁄ 2 1⁄ 2 1⁄ 4 3⁄ 4 1⁄ 2 1⁄ 4 3⁄ 4 1⁄ 8 7⁄ 8 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 21 / 19
Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to a perfectly balanced binary tree Pretend array is interval [0, 1] Find run boundaries closest to middle Recurse on both sides 1⁄ 2 1⁄ 2 1⁄ 4 3⁄ 4 1⁄ 2 1⁄ 4 3⁄ 4 1⁄ 8 7⁄ 8 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 21 / 19
Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to a perfectly balanced binary tree Pretend array is interval [0, 1] Find run boundaries closest to middle Recurse on both sides 1⁄ 2 1⁄ 2 1⁄ 4 3⁄ 4 1⁄ 2 1⁄ 4 3⁄ 4 1⁄ 8 7⁄ 8 split out of range! no node created Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 21 / 19
Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to a perfectly balanced binary tree Pretend array is interval [0, 1] Find run boundaries closest to middle Recurse on both sides 1⁄ 2 1⁄ 2 1⁄ 4 3⁄ 4 1⁄ 2 1⁄ 4 3⁄ 4 1⁄ 8 7⁄ 8 split out of range! no node created 1⁄ 2 1⁄ 4 3⁄ 4 1⁄ 8 7⁄ 815⁄ 16 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 21 / 19
Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to a perfectly balanced binary tree Pretend array is interval [0, 1] Find run boundaries closest to middle Recurse on both sides 1⁄ 2 1⁄ 2 1⁄ 4 3⁄ 4 1⁄ 2 1⁄ 4 3⁄ 4 1⁄ 8 7⁄ 8 split out of range! no node created 1⁄ 2 1⁄ 4 3⁄ 4 1⁄ 8 7⁄ 815⁄ 16 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 21 / 19
Mehlhorn: A best possible bound for the weighted path length of binary search trees, SIAM J Comp 1977 Intuition: “Round” to a perfectly balanced binary tree Pretend array is interval [0, 1] Find run boundaries closest to middle Recurse on both sides 1⁄ 2 1⁄ 2 1⁄ 4 3⁄ 4 1⁄ 2 1⁄ 4 3⁄ 4 1⁄ 8 7⁄ 8 split out of range! no node created 1⁄ 2 1⁄ 4 3⁄ 4 1⁄ 8 7⁄ 815⁄ 16 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 21 / 19
1.05 1.1 Powersort better merge cost #comparisons Scatter plot of relative costs Timsort Powersort Timsort better Worse on 2-3%, but if so, only slightly. On average, 3% fewer cmps and 5% less merge cost. Input: Runs of expected length √n, n = 105 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 22 / 19
1.05 1.1 Powersort better merge cost #comparisons Scatter plot of relative costs Timsort Powersort Timsort better Worse on 2-3%, but if so, only slightly. On average, 3% fewer cmps and 5% less merge cost. Input: Tim’s mixture of long and short runs Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 22 / 19
bad-example-mc random-permutations random-permutations2 random-sqrtn-runs random-sqrtn-runs2 random-sqrtn-runs3 words-of-bible Powersort faster Timsort faster Timsort faster Timsort faster Average running times Timsort Powersort CPython 3.11 with Powersort resp. Timsort selection of some “random” inputs all using int (cheap comparisons) machine-dependent, but qualitatively stable Machine 1 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 23 / 19
bad-example-mc random-permutations random-permutations2 random-sqrtn-runs random-sqrtn-runs2 random-sqrtn-runs3 words-of-bible Powersort faster Timsort faster Timsort faster Timsort faster Average running times Timsort Powersort CPython 3.11 with Powersort resp. Timsort selection of some “random” inputs all using int (cheap comparisons) machine-dependent, but qualitatively stable Machine 2 Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 23 / 19
Ware, Pause08, and Madebyoliver from www.flaticon.com. Vector graphics from Pressfoto, brgfx, macrovector and Jannoon028 on freepik.com Other photos from www.pixabay.com. Sebastian Wild Quicksort, Timsort, Powersort 2023-04-22 25 / 19