TIMSORT the sort in your language, and its proven bug
The default sort in Python, Java, Android, V8 and Rust is not quicksort or mergesort — it is Timsort, which finds the runs already in order and merges them, so nearly-sorted data flies through. It is fast, stable, and adaptive; it also carried a bug for years that a formal-methods team proved was there. It is array-and-merge work, so it runs in real I-13.
THE TECHNIQUE find runs, extend to minrun, merge
Scan for natural runs (maximal already-ascending, or strictly-descending, stretches); extend short ones to a computed minrun (32–64) with binary insertion sort; then merge runs while keeping a size invariant on the merge stack, using galloping (exponential search) when one run keeps winning. Below: the natural runs are coloured, then merged. live demo
HISTORY & CREDIT a proof that a shipping sort was wrong
The most-run sort on Earth — and for years it was subtly correct broken, in a way nobody hit until a prover looked. cited
2002 · Tim Peters writes Timsort for CPython’s list.sort() — an adaptive, stable, natural mergesort. It spreads to Java (object sort), Android, V8/Node, and Rust’s slice::sort. 2015 · Stijn de Gouw and colleagues, trying to prove the Java version’s merge-stack invariant with the KeY theorem prover, find the proof will not go through — and build a concrete input (~226 elements) that throws ArrayIndexOutOfBounds. The flaw was in Peters’s own 2002 code (merge_collapse checked only the top 3 runs, not 4), inherited by every port. Their paper: “OpenJDK’s sort is broken.” the lesson · the bug was not in exotic input — it was in the invariant the code assumed but never enforced, exactly the kind of gap a test suite misses and a proof catches. the fix · raise the stack size (or fix the invariant); the corrected version is what your runtime ships today.
A cautionary tale the corpus takes to heart: an instrument that assumes an invariant needs to enforce it, not trust it. proof beats test
RECOMMEND FOR I-13 runs + merge, on the array
Timsort is run-detection plus merging over one array — indexed reads, comparisons, and copies, the same array work counting-sort (049) and quicksort (045) already run:
$ i13 run merge.i13 # merge two sorted runs of a bounded array
merged = [1,2,3,4,5,7,8,10] # two runs -> one, stable
Recommend:nothing new — runs, insertion sort, and merge are bounded-array reads/writes with comparisons; no bignum, no bitwise. The one strain is the merge stack (a small stack of run boundaries) — itself a bounded array — and its invariant is exactly the sort of property I-13’s validator is built to declare: Timsort’s 2015 bug was an assumed-but-unenforced invariant, the corpus’s recurring warning. Note: galloping needs a binary search (dart 042, runs on the array); the whole algorithm is composition of no-walls the campaign already cleared.