Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Multiway Powersort

Multiway Powersort

Talk by Benjamin Smith for ALENEX 2023 about our paper: https://www.wild-inter.net/publications/cawley-gelling-nebel-smith-wild-2023

Sebastian Wild

March 24, 2023
Tweet

More Decks by Sebastian Wild

Other Decks in Research

Transcript

  1. MULTIWAY POWERSORT Ben Smith William Cawley Gelling, Markus E. Nebel,

    and Sebastian Wild University of Liverpool Monday 23rd January, 2023
  2. TIMSORT AND POWERSORT ▶ Tim Peters introduced Timsort in 2002

    • highly engineered version of mergesort • comparison based, internal, and stable • multiply adaptive: ▶ galloping merges ▶ run detection on the fly BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 1 / 16
  3. TIMSORT AND POWERSORT ▶ Tim Peters introduced Timsort in 2002

    • highly engineered version of mergesort • comparison based, internal, and stable • multiply adaptive: ▶ galloping merges ▶ run detection on the fly BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 1 / 16
  4. TIMSORT AND POWERSORT ▶ Tim Peters introduced Timsort in 2002

    • highly engineered version of mergesort • comparison based, internal, and stable • multiply adaptive: ▶ galloping merges ▶ run detection on the fly ▶ Timsort’s merge policy is less than optimal: • 1.5 times the optimal merge cost in the worst case (Buss and Knop 2018) • Hard to analyze • Prone to algorithmic bugs BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 1 / 16
  5. TIMSORT AND POWERSORT ▶ Tim Peters introduced Timsort in 2002

    • highly engineered version of mergesort • comparison based, internal, and stable • multiply adaptive: ▶ galloping merges ▶ run detection on the fly ▶ Timsort’s merge policy is less than optimal: • 1.5 times the optimal merge cost in the worst case (Buss and Knop 2018) • Hard to analyze • Prone to algorithmic bugs ▶ Munro and Wild introduced Powersort in 2018 • Merge policy update – retains most of Timsort • Optimal merge cost (up to lower order terms) • Built from first principles • Easy to analyze BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 1 / 16
  6. TIMSORT AND POWERSORT ▶ Tim Peters introduced Timsort in 2002

    • highly engineered version of mergesort • comparison based, internal, and stable • multiply adaptive: ▶ galloping merges ▶ run detection on the fly ▶ Timsort’s merge policy is less than optimal: • 1.5 times the optimal merge cost in the worst case (Buss and Knop 2018) • Hard to analyze • Prone to algorithmic bugs ▶ Munro and Wild introduced Powersort in 2018 • Merge policy update – retains most of Timsort • Optimal merge cost (up to lower order terms) • Built from first principles • Easy to analyze BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 1 / 16
  7. MERGE COST AND MERGE ORDER ▶ Merge cost: An abstract

    cost measure introduced by Buss and Knop (2018) ▶ For a single operation merging k runs, r0, . . . , rk−1 , the merge cost is given by: M = |r0 | + . . . + |rk−1 | BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 2 / 16
  8. MERGE COST AND MERGE ORDER ▶ Merge cost: An abstract

    cost measure introduced by Buss and Knop (2018) ▶ For a single operation merging k runs, r0, . . . , rk−1 , the merge cost is given by: M = |r0 | + . . . + |rk−1 | Merge order affects total merge cost (Example with k = 2) BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 2 / 16
  9. MERGE COST AND MERGE ORDER ▶ Merge cost: An abstract

    cost measure introduced by Buss and Knop (2018) ▶ For a single operation merging k runs, r0, . . . , rk−1 , the merge cost is given by: M = |r0 | + . . . + |rk−1 | Merge order affects total merge cost (Example with k = 2) BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 2 / 16
  10. MERGE COST AND MERGE ORDER ▶ Merge cost: An abstract

    cost measure introduced by Buss and Knop (2018) ▶ For a single operation merging k runs, r0, . . . , rk−1 , the merge cost is given by: M = |r0 | + . . . + |rk−1 | Merge order affects total merge cost (Example with k = 2) BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 2 / 16
  11. MERGE COST AND MERGE ORDER ▶ Merge cost: An abstract

    cost measure introduced by Buss and Knop (2018) ▶ For a single operation merging k runs, r0, . . . , rk−1 , the merge cost is given by: M = |r0 | + . . . + |rk−1 | ▶ An optimal merge tree minimizes total merge cost ▶ Goal: A nearly optimal merge tree with low overhead costs Merge order affects total merge cost (Example with k = 2) BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 2 / 16
  12. (2-WAY) POWERS AND THE VIRTUAL PERFECTLY BALANCED BINARY TREE 44

    45 46 47 48 49 50 41 42 43 40 39 33 34 35 36 37 38 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 11 12 13 14 15 16 10 7 8 9 1 2 3 4 5 6 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 3 / 16
  13. (2-WAY) POWERS AND THE VIRTUAL PERFECTLY BALANCED BINARY TREE 44

    45 46 47 48 49 50 41 42 43 40 39 33 34 35 36 37 38 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 11 12 13 14 15 16 10 7 8 9 1 2 3 4 5 6 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 1 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 3 / 16
  14. (2-WAY) POWERS AND THE VIRTUAL PERFECTLY BALANCED BINARY TREE 44

    45 46 47 48 49 50 41 42 43 40 39 33 34 35 36 37 38 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 11 12 13 14 15 16 10 7 8 9 1 2 3 4 5 6 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 1 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 3 / 16
  15. (2-WAY) POWERS AND THE VIRTUAL PERFECTLY BALANCED BINARY TREE 44

    45 46 47 48 49 50 41 42 43 40 39 33 34 35 36 37 38 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 11 12 13 14 15 16 10 7 8 9 1 2 3 4 5 6 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 1 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 3 / 16
  16. (2-WAY) POWERS AND THE VIRTUAL PERFECTLY BALANCED BINARY TREE 44

    45 46 47 48 49 50 41 42 43 40 39 33 34 35 36 37 38 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 11 12 13 14 15 16 10 7 8 9 1 2 3 4 5 6 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 1 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 3 / 16
  17. (2-WAY) POWERS AND THE VIRTUAL PERFECTLY BALANCED BINARY TREE 44

    45 46 47 48 49 50 41 42 43 40 39 33 34 35 36 37 38 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 11 12 13 14 15 16 10 7 8 9 1 2 3 4 5 6 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 1 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 3 / 16
  18. (2-WAY) POWERS AND THE VIRTUAL PERFECTLY BALANCED BINARY TREE 44

    45 46 47 48 49 50 41 42 43 40 39 33 34 35 36 37 38 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 11 12 13 14 15 16 10 7 8 9 1 2 3 4 5 6 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 1 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 3 / 16
  19. (2-WAY) POWERS AND THE VIRTUAL PERFECTLY BALANCED BINARY TREE 44

    45 46 47 48 49 50 41 42 43 40 39 33 34 35 36 37 38 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 11 12 13 14 15 16 10 7 8 9 1 2 3 4 5 6 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 1 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 3 / 16
  20. (2-WAY) POWERS AND THE VIRTUAL PERFECTLY BALANCED BINARY TREE 44

    45 46 47 48 49 50 41 42 43 40 39 33 34 35 36 37 38 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 11 12 13 14 15 16 10 7 8 9 1 2 3 4 5 6 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 1 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 3 / 16
  21. (2-WAY) POWERS AND THE VIRTUAL PERFECTLY BALANCED BINARY TREE 3

    4 5 2 1 3 2 4 3 44 45 46 47 48 49 50 41 42 43 40 39 33 34 35 36 37 38 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 11 12 13 14 15 16 10 7 8 9 1 2 3 4 5 6 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 1 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 3 / 16
  22. (2-WAY) POWERS AND THE VIRTUAL PERFECTLY BALANCED BINARY TREE 3

    4 5 2 1 3 2 4 3 44 45 46 47 48 49 50 41 42 43 40 39 33 34 35 36 37 38 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 11 12 13 14 15 16 10 7 8 9 1 2 3 4 5 6 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 1 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 3 / 16
  23. (2-WAY) POWERS AND THE VIRTUAL PERFECTLY BALANCED BINARY TREE 3

    4 5 2 1 3 2 4 3 44 45 46 47 48 49 50 41 42 43 40 39 33 34 35 36 37 38 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 11 12 13 14 15 16 10 7 8 9 1 2 3 4 5 6 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 1 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 3 / 16
  24. (2-WAY) POWERS AND THE VIRTUAL PERFECTLY BALANCED BINARY TREE 3

    4 5 2 1 3 2 4 3 44 45 46 47 48 49 50 41 42 43 40 39 33 34 35 36 37 38 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 11 12 13 14 15 16 10 7 8 9 1 2 3 4 5 6 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 1 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 3 / 16
  25. POWERS ARE LOCAL 4 44 45 46 47 48 49

    50 41 42 43 40 39 33 34 35 36 37 38 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 11 12 13 14 15 16 10 7 8 9 1 2 3 4 5 6 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 1 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 4 / 16
  26. CALCULATING MERGE POWERS ▶ For run lengths L0, . .

    . , Lr−1, first set li = Li n , then: • Define ai , the normalized centre of the (i − 1)st run: ai = i−1 j=0 lj − 1 2 li−1, • Define bi , the normalized centre of ith run: bi = i−1 j=0 lj + 1 2 li • Hence, define the power of the boundary between these runs, Pk i : Pk i = min{p ∈ N : ⌊ai · kp⌋ < ⌊bi · kp⌋} BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 5 / 16
  27. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs a b c d e f 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  28. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs a b c d e f 3 run1 run2 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  29. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs a b c d e f 3 run1 run2 a – 3 run stack 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  30. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs a b c d e f 3 2 run1 run2 a – 3 run stack 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  31. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs a b c d e f 3 2 run1 run2 a – 3 b – 2 run stack 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  32. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs a b c d e f 3 2 run1 run2 a – 3 b – 2 run stack 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  33. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs a b c d e f 3 2 run1 run2 a – 3 b – 2 run stack merge 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  34. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs ab c d e f 2 run2 ab – 2 run stack 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  35. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs ab c d e f 2 1 run1 run2 ab – 2 run stack 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  36. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs ab c d e f 2 1 run1 run2 ab – 2 c – 1 run stack 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  37. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs ab c d e f 2 1 run1 run2 ab – 2 c – 1 run stack 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  38. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs ab c d e f 2 1 run1 run2 ab – 2 c – 1 run stack merge 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  39. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs abc d e f 1 run2 abc – 1 run stack 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  40. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs abc d e f 1 2 run1 run2 abc – 1 run stack 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  41. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs abc d e f 1 2 run1 run2 abc – 1 d – 2 run stack 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  42. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs abc d e f 1 2 4 run1 run2 abc – 1 d – 2 run stack 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  43. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs abc d e f 1 2 4 run1 run2 abc – 1 d – 2 e – 4 run stack 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  44. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs abc d e f 1 2 4 abc – 1 d – 2 e – 4 run stack 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  45. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs merge-down phase abc d e f 1 2 4 abc – 1 d – 2 e – 4 run stack 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  46. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs merge-down phase abc d e f 1 2 4 abc – 1 d – 2 e – 4 run stack merge 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  47. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs merge-down phase abc d ef 1 2 abc – 1 d – 2 run stack 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  48. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs merge-down phase abc d ef 1 2 abc – 1 d – 2 run stack merge 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  49. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs merge-down phase abc def 1 abc – 1 run stack 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  50. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs merge-down phase abc def 1 abc – 1 run stack merge 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  51. 2-WAY POWERSORT 1 procedure Powersort(𝐴[0..𝑛)) 2 𝑖 := 0; runs

    := new Stack() 3 𝑗 := ExtendRunRight(𝐴, 𝑖) 4 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 5 while 𝑖 < 𝑛 6 𝑗 := ExtendRunRight(𝐴, 𝑖) 7 𝑝 := power(runs.top(), (𝑖, 𝑗), 𝑛) 8 while 𝑝 ≤ topmost power 9 merge topmost 2 runs 10 runs.push(𝑖, 𝑗); 𝑖 := 𝑗 11 while runs.size() ≥ 2 12 merge topmost 2 runs abcdef 24 25 26 27 28 21 22 23 18 19 20 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 1 2 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 6 / 16
  52. WHY MERGE MULTI-WAY? ▶ Memory transfer costs have become a

    tighter bottleneck than Processor costs in various sorting algorithms (Kushagra et.al., 2014) • But it’s a close run thing! ▶ To reduce these costs, take inspiration from external memory techniques/algorithms • Specifically, k-way merging ▶ Tuning is important: • Low k reduces Processor costs and is easy to implement • High k reduces Memory costs (I/Os) but is harder to implement • Optimal value depends on data type, hardware, language,.. . BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 7 / 16
  53. 4 WAY MERGING 3 4 5 2 1 3 2

    4 3 44 45 46 47 48 49 50 41 42 43 40 39 33 34 35 36 37 38 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 11 12 13 14 15 16 10 7 8 9 1 2 3 4 5 6 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 1 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 8 / 16
  54. 4 WAY MERGING 3 4 5 2 1 3 2

    4 3 44 45 46 47 48 49 50 41 42 43 40 39 33 34 35 36 37 38 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 11 12 13 14 15 16 10 7 8 9 1 2 3 4 5 6 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 1 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 2 2 3 1 1 2 1 2 2 44 45 46 47 48 49 50 41 42 43 40 39 33 34 35 36 37 38 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 11 12 13 14 15 16 10 7 8 9 1 2 3 4 5 6 3 3 3 2 3 3 3 2 3 3 3 2 3 3 3 1 3 3 3 2 3 3 3 2 3 3 3 2 3 3 3 1 3 3 3 2 3 3 3 2 3 3 3 2 3 3 3 1 3 3 3 2 3 3 3 2 3 3 3 2 3 3 3 BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 8 / 16
  55. MULTIWAY MERGING ▶ New possibility: can now have multiple merges

    on the stack with the same power ▶ Handle but using a multi-way merge ▶ Specifically, a Winner tree, using sentinels wherever possible BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 9 / 16
  56. RESULTS 1: RUNS OF EXPECTED LENGTH √ n, I N

    TS 4 5 6 7 8 1.4 1.6 1.8 2.0 2.2 running time (int, random runs) 4-way Powersort 4-way Powersort (no sentinels) 2-way Powersort 2-way Powersort (no sentinels) 2-way Powersort (buffer smaller run only) std::sort std::stable_sort top-down mergesort ▶ Normalized running times against log10 (n). 320 340 360 380 400 running time (107 ints, random runs) 4-way Powersort 4-way Powersort (no sentinels) 2-way Powersort 2-way Powersort (no sentinels) 2-way Powersort (buffer smaller run only) ▶ Distributions of running time in ms for the same data BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 10 / 16
  57. RESULTS 2: RUNS OF EXPECTED LENGTH √ n, L O

    N G + POINTER 4 5 6 7 8 1.5 2.0 2.5 3.0 running time (long+pointer, random runs) 4-way Powersort 4-way Powersort (no sentinels) 2-way Powersort 2-way Powersort (no sentinels) 2-way Powersort (buffer smaller run only) std::sort std::stable_sort top-down mergesort ▶ Normalized running times against log10 (n). 400 450 500 550 running time (107 long+ptr, random runs) 4-way Powersort 4-way Powersort (no sentinels) 2-way Powersort 2-way Powersort (no sentinels) 2-way Powersort (buffer smaller run only) ▶ Distributions of running time in ms for the same data BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 11 / 16
  58. RESULTS 3: RANDOM PERMUTATIONS, I N TS 4 5 6

    7 8 2.8 3.0 3.2 3.4 running time (int, rand. perm.) 4-way Powersort 4-way Powersort (no sentinels) 2-way Powersort 2-way Powersort (no sentinels) 2-way Powersort (buffer smaller run only) std::sort std::stable_sort top-down mergesort ▶ Normalized (time / n lg n) running times against log10 (n). ▶ note that std::sort in C++ is intro sort – not a stable method BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 12 / 16
  59. RESULTS 4: RUNS OF EXPECTED LENGTH √ n, I N

    TS 4 5 6 7 8 0.5 1.0 1.5 2.0 2.5 3.0 3.5 scanned elements (int, random runs) 4-way Powersort 2-way Powersort (buffer smaller run only) 2-way Powersort top-down mergesort ▶ Normalized merge cost against log10 (n). BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 13 / 16
  60. CONCLUSION ▶ Findings • 4-way Powersort can yield significant performance

    improvements • This can be explained by its reduced merge cost • Some of these results rely on the use of sentinels BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 14 / 16
  61. CONCLUSION ▶ Findings • 4-way Powersort can yield significant performance

    improvements • This can be explained by its reduced merge cost • Some of these results rely on the use of sentinels ▶ Further Work • Fast multi-way merging without simple sentinels • Study multi-way powersort in a wider technological context • Compare multi-way powersort with more competitors, specifically multiway quicksort variants. BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 14 / 16
  62. CONCLUSION ▶ Findings • 4-way Powersort can yield significant performance

    improvements • This can be explained by its reduced merge cost • Some of these results rely on the use of sentinels ▶ Further Work • Fast multi-way merging without simple sentinels • Study multi-way powersort in a wider technological context • Compare multi-way powersort with more competitors, specifically multiway quicksort variants. ▶ Recommendations • Users of Timsort should seriously consider the Powersort merge policy • Users of Timsort and 2-way powersort may wish to consider multi-way Powersort ▶ Particularly where comparisons are cheap and sentinels are useable BEN SMITH WILLIAM CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 14 / 16
  63. RESULTS 5: TIME AS FUNCTION OF PRESORTEDNESS BEN SMITH WILLIAM

    CAWLEY GELLING, MARKUS E. NEBEL, AND SEBASTIAN WILD 16 / 16