Powersort's Pursuit

My colleague Tony McCabe put a game implementation of merging policies together, where you can try to find the minimal-mergecost order of merges.

Below are a few example inputs to try. You have to drag&drop one run over one of its neighbors to merge them; this costs you the sum of their lengths. The goal is to merge up all runs with minimal total cost.

LEGO input: 4 2 2 1 3 3   Example from talk: 8 2 2 2 3 1   Example from ESA paper: 5 3 3 14 1 2   Extremes: 2 4 6 3 2 4 234 112 2

Bad for Timsort: 110 10 10 10 10 15 15 15 15   Tricky input: 60 19 20 9 5 25 99 28

Connection to sorting

The game captures exactly the optimization problem that Timsort and Powersort face: The boxes are existing sorted runs in the data that we have to merge in pairs until we eventually have a single sorted run. The cost of merging is (slightly simplistically) set to the size of the output. For a stable sort, we can only merge adjacent runs.