the insertion-sort invariant proof

Insertion sort is how many people sort a hand of playing cards: keep the cards in your left hand sorted, pick up the next card, and slide it leftward until it sits in the right spot among the sorted ones. The pile you have already arranged grows by one each time, and it stays sorted. Turning that intuition into a proof is the textbook example of a loop invariant, and it shows the whole machinery (initialization, maintenance, termination) on a tiny, concrete algorithm.

The algorithm: for i from 2 to n, take key = A[i] and insert it into the already-sorted prefix A[1..i-1] by shifting larger elements right. The loop invariant is: at the start of each iteration for index i, the subarray A[1..i-1] consists of the original elements that were there, now in sorted order. Initialization: when i = 2, A[1..1] is a single element, trivially sorted and unchanged — the invariant holds. Maintenance: assume A[1..i-1] is sorted; the inner loop shifts every element greater than key one position right and drops key into the gap, so afterwards A[1..i] is sorted and contains the same elements; incrementing i restores the invariant for the next pass. Termination: the loop ends when i = n+1, so the invariant reads 'A[1..n] is sorted and a permutation of the original' — which is exactly the postcondition.

This proof is the canonical illustration of why invariants work: each of the three parts is small and checkable, yet together they certify the result for arrays of every size and every initial order, including duplicates and already-sorted input. Note two honesty points. First, this argues correctness, not speed: insertion sort is still O(n^2) in the worst case even though it is correct. Second, the invariant must include 'a permutation of the original' — shifting never creates or destroys elements — or the proof would not rule out a procedure that sorts by overwriting everything with zeros.