Split, sort the halves, merge them back — the oldest recursive idea in computing, written by hand by von Neumann in 1945 as one of the very first programs. It is stable, always n log n, and the ancestor of Timsort (dart 066). Its merge step runs on I-13’s array.
THE TECHNIQUE merge adjacent runs, doubling the width
The historical form is bottom-up: treat the array as runs of length 1; each pass merges adjacent runs of width 1, 2, 4, 8…, doubling; after log n passes the whole array is one sorted run. To merge two sorted runs, walk both with a pointer and emit the smaller (ties from the left — that is what makes it stable). Watch the widths double. live demo
HISTORY & CREDIT the first program was a sort
Textbooks draw it recursively top-down — von Neumann’s real 1945 program was bottom-up, and it was never run (no computer existed yet). cited
pre-1945 · punched-card collators already mesh two sorted decks — the merge idea predates electronics. 1945 · John von Neumann hand-writes a meshing (merge) sort for the proposed EDVAC — a paper program, written partly to stress-test whether the new stored-program instruction set could do a non-numerical job. Sorting was IBM’s commercial turf; proving a general computer could sort was pointed. 1948 · Goldstine & von Neumann publish the coded, timed bottom-up version. 1970 · Knuth, in “Von Neumann’s First Computer Program,” transcribes and credits it — sorting was among the very first things anyone wrote code for.
Stable and sequential-access, it became the archetypal external sort of the tape era — and, as natural merge, the heart of Timsort. von Neumann, 1945
RECOMMEND FOR I-13 the merge runs on the array
Merge is two read pointers and one write pointer over bounded arrays — and it runs on the real compiler (merge two sorted runs into one, stably):
$ i13 run merge.i13 # merge [1,3,5,8] and [2,4,7,10]
out[0] = 1 out[5] = 7 # -> [1,2,3,4,5,7,8,10], ties from the left
Recommend:nothing new — the bottom-up form is the natural fit: a width-doubling loop over the array plus a second f64 array as the O(n) buffer, no recursion needed. Stability is the ≤-tie rule (emit from the left run on equality). Merge is a two-run-in, one-run-out pass — a clean motivating case for the paired-array / PS-004 want — and it is exactly the merge Timsort (066) builds on. Note: quicksort (045) partitions in place; merge sort trades an O(n) buffer for a guaranteed n log n and stability — the trade the whole sorting family is organised around.