Pick a pivot, throw everything smaller to its left and larger to its right, then sort each side the same way. Quicksort is one of the most-used algorithms ever written — conceived by a young British student in Moscow, translating Russian. Its partition runs in real I-13 on the new array; its recursion reveals the next wall — the one the array just uncovered.
THE TECHNIQUE partition around a pivot, recurse
Choose a pivot (orange). Sweep through, moving every smaller element to the front; the pivot settles into its final sorted position, with all smaller left and larger right. Recurse on each side. Watch it sort. live demo
HISTORY & CREDIT a sort born in translation
Imagined as a dry CS result — it was actually invented to sort numbers look up Russian words in a dictionary. cited
1959–60 · Tony Hoare, 25, a British exchange student in Moscow (in the milieu of Kolmogorov — the same seminar culture that produced Karatsuba, dart 041), works on machine translation. To translate a sentence he must look each word up in a dictionary — faster if the words are sorted first. the idea · he invents partition-and-recurse; but could not write it down — he had no way to express recursion until he learned ALGOL 60. 1961 · published as Algorithm 64 in Communications of the ACM — barely a page. after · average O(n log n), in-place, cache-friendly; still the default sort in countless libraries sixty years on.
The most practical sort in the world began as a way to read Russian. canonical
RECOMMEND FOR I-13 the array’s success reveals the next wall
One Lomuto partition pass runs in real I-13 — it rearranges the array around the pivot and returns it:
$ i13 run partition.i13 # pivot = a[7] = 5
pivot = 5
e0 = 2 # smaller elements moved to the front, larger to the back
But full quicksort’s recursion needs the partition to hand back two things at once — the rearranged arrayand the pivot’s final index — to split qsort(a, lo, p) from qsort(a, p+1, hi). An I-13 function returns exactly one value:
no way to return (array, index) as a pair — single return only.
Recommend: a way to return more than one value — a small tuple / pair, or an out-parameter convention. This is the newest wall in the whole campaign, and it is telling: the array the author just added cleared the aggregate wall, and the very next classic algorithm reveals the edge behind it. The frontier moved. Honest note: a sort does run today — bubble and insertion sort thread a single array cleanly (verified). Quicksort specifically wants the dual return. Two open recommends now stand: multiple return (this dart) and bignum (darts 032/035/036/041).