sorted-check lab · mode 1 of 2 · run editor

One `if` before the merge.
Move the runs and watch it pay.

Plain top-down mergesort, plus a single test: after sorting both halves, merge only when A[m-1] > A[m]. A call whose whole range sits inside one run fails that test and pays nothing. This is not the run-adaptive framework — there is no run decomposition and no merge tree over runs, just the fixed dyadic recursion with some of its merges switched off. Drag the run strip at the bottom of the tree; everything above it is rebuilt on every change.

recursion tree · faded = merge skipped

merge cost —

delay

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 space play f present

metrics

legend

subdivision entropy H_S

Top-down mergesort cuts every run along the recursion grid, so it behaves exactly as if the input had been the subdivided profile below: each run is split into the maximal recursion-tree nodes it contains. H_S is the run-length entropy of that profile. Merge cost equals n·H_S exactly when n is a power of two, and sits just above it otherwise.

Applying it twice changes nothing — the subdivision is its own fixed point, which is the quickest check that the equivalence is real.

generate

n runs

the chain, level by level —

per level: bound min{L, 2n/2^d} (pale) vs. actually charged (solid)

the three steps

where the 3 comes from: g(f) = 2 − f + 2^f

charging scheme — proof of cost ≤ (H+3)n

Split every counted merge's cost at run boundaries: run i is charged its overlap with each straddling node. The green/red cut is by level: the top G = ⌊lg(2n/l_i)⌋ levels are green. At most 2 active nodes per level can overlap a run — one holding each endpoint; anything strictly inside straddles no boundary and the sorted check skips it. Since every subproblem on level d has size ≤ ⌈n/2^d⌉ (all n, not just powers of two), the level-d charge is ≤ min{l_i, 2n/2^d}, which sums to (G+1)l_i + 2n/2^G ≤ l_i·lg(n/l_i) + 3l_i. Summing over runs gives nH + 3n. The last two columns are the two upper bounds, in the order they are applied. Hover any charged part (with charging colours on) for the level-by-level breakdown; the per-run excess average depth is in the metrics panel.

sorted-check lab · mode 2 of 2 · adversarial search

Throw run profiles at it.
See what breaks.

Searching compositions is exhaustive over inputs: for a fixed run-length profile the reverse-ordered construction attains the maximum cost of any array with that profile, so nothing is missed by only moving run boundaries. Push (cost − nH)/n, H_S − H or the excess average depth and see whether any of them gets past 3. Ticking a conjecture turns the search into a counterexample hunt.

random input n runs

current input

drag a boundary to resize · drag a run past its neighbour to swap · ←→ select ↑↓ resize u undo

sweep — best found per n

click a row to load that profile into the editor

hall of fame — worst inputs found this session

nothing yet — run a search.

adversarial search

by maximising

b n n value

runs runs value samples / restarts

sweep n over

sample + climb draws structured random profiles (uniform compositions, alternating tiny/large, one-big-rest-singletons, geometric blocks), then hill-climbs from the best one by local edits — resize, rescale, split, delete, insert. climb from current skips the sampling and starts from the input in the editor.

extremify repeatedly makes the shortest runs shorter and the longest runs longer, taking the best improving polarising move each round, until nothing improves. The run count never changes; n is free to move up to the n value unless n is fixed.

anneal boundaries simulated-anneals over boundary sets with an O(log n) incremental evaluator, at a pinned n. exhaustive enumerates all 2ⁿ⁻¹ boundary sets by a Gray-code walk, so it is a proof for that n.

Ticking a conjecture below turns any of these into a counterexample hunt: it stops the moment that conjecture fails.

conjectures

checked live against the input in the editor. Tick the box to make the search stop on a violation.

One if before the merge.Move the runs and watch it pay.

Throw run profiles at it.See what breaks.

One `if` before the merge.
Move the runs and watch it pay.

Throw run profiles at it.
See what breaks.