THE INSERTION SORT how you sort a hand of cards — and it beats the clever ones when nearly sorted
Insertion sort grows a sorted region one element at a time: take the next value, slide the larger sorted elements right, and drop it into the gap — exactly how you arrange a hand of playing cards. It is O(n²) in the worst case, but on nearly-sorted data it runs in almost linear time, and it is fast for tiny arrays with negligible overhead. That is why real hybrid sorts (Timsort, introsort) fall back to insertion sort for small runs. It is stable, in-place, and the quiet workhorse inside the fast sorts.
THE TECHNIQUE slide larger elements right, drop the key in — O(n²), fast when near-sorted
The demo insertion-sorts [5,2,4,1,3] by inserting each element into the growing sorted prefix: live demo
HISTORY & CREDIT insertion sort · the card-hand sort
“Quadratic sorts are useless.” — insertion sort is near-linear on nearly-sorted data and the fastest choice for small runs. cited
the insert · shift the larger sorted elements right, drop the key into the opened gap. the edge · near-linear on nearly-sorted input; tiny constant — best for small arrays. the role · the small-run fallback inside Timsort and introsort — stable, in-place.
Each value slid into its place in a growing sorted hand — quadratic in the worst case, near-linear when it counts. resource
RECOMMEND FOR I-13 the inserted sort, on the compiler
On the canonical compiler, insertion sort turns [5,2,4,1,3] into a sorted list (first 1, last 5):
$ i13 run or_insertionsort.i13 # shift and drop the key
RUN OK · 503 step(s) · peak stack 6 · call depth 7
is_sorted = 1 first = 1 last = 5
Recommend as a NULL — resource, the adaptive kind. Insertion sort yields the same sorted output as any sort, with a cost that adapts to how sorted the input already is (B40). It is stable and the small-run engine inside the fast sorts. NULL — quadratic on paper, indispensable in practice.