APE Cram
cs.jdoner.me · sorting Insertion Sort
Order The official advice is to do Sorting before Files. Insertion sort is fast on nearly-sorted data and stable.
Half beats none A method that does half the job and compiles beats one that does the whole job and does not.
{{ pz.rung }}

{{ pz.title }}

{{ pz.overload }}

{{ pz.brief }}

Goal {{ pz.goalText }}
Scores 0 {{ pz.zeroTrap }}
Then: guided walkthrough
{{ c.v }}
{{ c.idx }}
{{ swap.va }}
{{ swap.vb }}
i
j
Swap speed
pass {{ ctl.pass }} missteps {{ ctl.attempts }}
Array after
each pass

This is the diff: Main prints the sorted array, and your last row must match it.

{{ r.label }}
{{ c.v }}
{{ r.note }}
Why is Insertion Sort stable?

A sorting algorithm is stable if duplicate elements keep their original relative order. Insertion sort achieves this through its loop condition: while (j >= 0 && a[j] > current).

Because it uses a strict greater-than (>) test, the loop will not shift an element right if it is equal to the current one. The new element stops immediately after any existing duplicates, perfectly preserving their original sequence.

Wait, how is this different from Selection Sort?

Selection sort is completely blind to the data. It always does exactly n-1 swaps and approximately n² / 2 comparisons, regardless of whether the array is already sorted or completely reversed. It is also not stable.

Insertion sort is adaptive. Because its inner loop stops as soon as it finds a smaller element, it performs incredibly well on nearly-sorted data. A completely sorted array is its best case: it does exactly n comparisons and 0 shifts (a linear O(n) time). Its worst case is a reversed array, where it must shift every element all the way down, resulting in the same n² / 2 comparisons as selection sort. And unlike selection sort, it is stable.

{{ hint.head }}

{{ hint.body }}
Matches the comment

{{ draw.why }}

{{ draw.text }}

On the APE you write this sort by hand from a provided Main, then diff the printed array against the comment. A built-in sort() scores 0. You just traced every pass yourself.