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.



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.