merge policy workshop · mode 1 of 3 · run editor

Your rule. Your tree.
Your bill.

A stable run-adaptive mergesort is fully described by its merge tree: the leaves are the runs of the input, every internal node is one merge, and the merge cost is the sum of the lengths of all internal nodes. The one policy built into this page is deliberately dumb — it always merges the two rightmost blocks and never looks at a length. Your job is to write a better rule, in Python, in the editor below. Edit the runs and the tree of the selected policy is rebuilt on every change; the cost meter tells you how far above the entropy bound nH you are.

merge policy

merge cost —

drag a boundary to resize two runs · drag a run past its neighbour to swap · click to select · ←→ select ↑↓ resize (shift ×10) s split j join d duplicate x delete ,. swap u undo

policy code

loading Python…

how to write a policy — the API, with examples

A policy is one Python function. It receives the run lengths of the input, left to right, and it does not sort anything — it only decides in which order neighbouring blocks are merged, and reports that order as a list of merges:

def policy(runs):          # runs = [5, 3, 3, 14, 1, 2], say
    merges = []
    ...
    return merges

Every input of r runs needs exactly r − 1 merges. There are two ways to say which blocks a merge joins; use one of them for the whole list.

style 1 · positions — “merge blocks k and k+1”

An entry k means: merge the blocks that are currently at positions k and k+1, counted from the left over all current blocks (0-based). Order matters: the list of blocks gets one shorter with every merge. This is the natural style for rules that scan or that keep a stack. If your stack holds the blocks read so far, stack[i] is block i, so merging stack[i] and stack[i+1] is simply the merge i, and “merge the top two” is len(stack) - 2:

def policy(runs):
    stack = []                       # the blocks read so far, bottom ... top
    merges = []
    for length in runs:
        stack.append(length)
        while len(stack) >= 2 and stack[-1] >= stack[-2]:      # a first guess -- replace it
            merges.append(len(stack) - 2)                      # merge the top two
            stack[-2:] = [stack[-2] + stack[-1]]
    while len(stack) > 1:            # whatever is left must still be merged
        merges.append(len(stack) - 2)
        stack[-2:] = [stack[-2] + stack[-1]]
    return merges

style 2 · spans — “merge everything from run i to run j”

An entry (i, j) means: merge the two blocks that together cover the original runs i … j (0-based, inclusive). Order does not matter — spans are sorted so smaller ones go first — which makes this the natural style for recursive, top-down rules:

def policy(runs):
    merges = []
    def split(i, j):                 # build the tree for runs i..j
        if i == j:
            return
        k = (i + j) // 2             # cut after run k -- here: by run count, ignoring lengths
        merges.append((i, j))
        split(i, k)
        split(k + 1, j)
    split(0, len(runs) - 1)
    return merges

what you get back

The page checks the merges and, if something is off, tells you what: a position out of range, a span that crosses another, too few or too many merges, a forgotten return.
print(...) inside your policy shows up in the box above — handy for debugging. import math and the rest of the standard library work as usual.
Your code is saved in this browser as you type, and download .py gives you a file that check_policy.py (from the workshop folder) can test from the command line.
An endless loop freezes the page. Reload; your code will still be there.

Read merge cost as “elements written”: a merge of blocks of length a and b costs a + b. nH (n times the entropy of the run lengths) is a lower bound no policy can beat.

merge policy workshop · mode 3 of 3 · random inputs & adversarial search

Throw inputs at it.
See what breaks.

Generate a random input, and every policy’s tree is drawn at once — with highlight differences to see where they diverge. Then let the search loose: it samples thousands of inputs looking for the one that makes a chosen policy look worst (highest cost above nH, or worse than a rival). Write down what you believe about your policy as a conjecture — “never more than n(H + 2)”, say — tick it, and the search stops the instant it finds a counterexample.

random input n runs

every policy on this input

highlight differences reference order

adversarial search

make this policy look bad by maximising

n n value runs runs value samples

always load the worst input found (uncheck to only report it)

search samples random inputs, then hill-climbs from the best one by local edits. extremify repeatedly makes the shortest runs shorter and the longest runs longer, for as long as the metric improves; the number of runs never changes. exhaustive checks every composition in range and respects the n/runs mode toggles: fixed checks exactly that value, up to every value from the minimum up through it. If that space is large it says so and waits. Python policies are slower than the built-in one — keep n and the run count modest and grow them once things look good.

Ticking a conjecture below turns the search into a hunt for a counterexample: it stops the moment that conjecture fails.

current input

conjectures

Two claims per policy, checked live against the input on the left. The numbers are yours to edit: how far above nH do you believe your policy can be driven? Tick the box to make the search stop on a violation.

hall of fame — worst inputs found this session

nothing yet — run a search.

Your rule. Your tree.Your bill.

style 1 · positions — “merge blocks k and k+1”

style 2 · spans — “merge everything from run i to run j”

what you get back

One input.Every rule in the room.

Throw inputs at it.See what breaks.

Your rule. Your tree.
Your bill.

One input.
Every rule in the room.

Throw inputs at it.
See what breaks.