Sorting Race

Algorithms & Data

Quicksort, heapsort and mergesort race to sort the same shuffled array of 32 bars on a Super Nintendo — you watch which finishes first. The two recursive sorts push the 65816's soft stack / frame ABI; heapsort runs iteratively as the contrast. Runs automatically; no joypad needed. Written in C and compiled with the llvm-mos-based 65816 toolchain (+mos-a16, 16-bit accumulator mode).

loading core…

Self-running demo — the three sorts race automatically, then reshuffle.

Click the screen to focus, then watch. Tab away and it pauses.

What it is

Three classic comparison sorts run on three copies of the same shuffled array, stacked as three bands — quicksort (red), heapsort (green) and mergesort (blue). Each bar's height is its value; as a sort runs, the bars climb into a clean ascending ramp. The label under each band counts the moves (M) and comparisons (C) and flips to DONE when that sort finishes — and the footer names the winner. Then it reshuffles and races again.

Quicksort and mergesort are written as ordinary recursive functions; heapsort is an iterative loop. The animation is record/replay: each sort runs to completion first, logging every element it writes, and the screen replays that log one step per frame:

qsort(a, lo, hi):                  // genuine recursion
    if lo >= hi: return
    pivot = a[(lo+hi)/2]
    partition a around pivot       // swaps -> op-log
    qsort(a, lo, j)                // the array pointer is
    qsort(a, i, hi)                //   live across the self-call

That recursive self-call is the point: a pointer into the array stays live across it, so the compiler must spill it to the software stack in WRAM (the 65816's hardware stack is only 256 bytes). Keeping recursion in the real sort — instead of rewriting it as an explicit-stack loop for the animation — is what makes this a faithful test of that path.

Compiler stress-test #17 — the recursion one

Each demo in this gallery targets one corner of the compiler. This is the recursion / soft-stack / frame-ABI member: no 32-bit multiply or divide at all, just recursive control flow and a lot of compares.

Item	What it exercises
Recursion	Quicksort and mergesort are genuinely recursive — each call frame holds a pointer into the array that must stay live across the self-call. That forces the backend's reentrant soft-stack spill path, the exact corner this demo exists to exercise
Soft stack / frame ABI	The 65816 has a 256-byte hardware stack, so the toolchain spills reentrant locals to a software stack in WRAM. A mid-pivot quicksort + top-down mergesort on 32 elements keeps depth shallow (O(log N)) — deep enough to prove the path, safe against overflow
Iterative contrast	Heapsort uses a loop-based sift-down — no recursion at all. Racing it against the two recursive sorts puts the recursive and iterative shapes side by side in one program
Op-log record/replay	Each sort runs to completion writing a log of (position := value) stores; the screen replays one store per algorithm per frame. So the REAL recursive sort is the compiler stress — the animation never rewrites it into an explicit-stack loop
Three-way self-check	The gate sorts the same shuffle three ways and asserts all three produce the identical 0..31 order before folding the hash — a miscompiled sort that reorders wrongly is caught, not just hashed over
rep/sep	Native 16-bit accumulator brackets under +mos-a16 — 233 occurrences across the compare-heavy inner loops and array indexing. No 32-bit math libcalls: this demo is about control flow, not wide arithmetic

The sort engine is a portable C header (examples/65816/sort-race.h) linked into the SNES ROM and a host oracle alike. The gate folds 8 rounds — each reshuffles, sorts three ways, asserts all three agree on the sorted order, then folds each algorithm's compare/move counts — into a 16-bit CRC that must be identical on host and target.

Written in C with the llvm-mos 65816 toolchain. Hit Verify fidelity to reproduce the build gate's WRAM assert (gate CRC 0xB28F) live in this tab — the same hash the host oracle and the cycle-accurate bsnes-jg core agree on. The disasm gate proves the shape: recursive sr_qsort/sr_msort present, rep/sep = 233, and zero 32-bit arithmetic libcalls.