Correctness with loop invariants
Prove that insertion sort is correct by checking an invariant before every iteration.
def insertion_sort(values):
items = list(values)
for i in range(1, len(items)):
assert items[:i] == sorted(items[:i])
key = items[i]
j = i - 1
while j >= 0 and items[j] > key:
items[j + 1] = items[j]
j -= 1
items[j + 1] = key
assert items == sorted(items)
return items
print(insertion_sort([5, 2, 4, 6, 1, 3]))
print(insertion_sort([]))[1, 2, 3, 4, 5, 6] []
Explanation
Analysis covers correctness as well as speed: an algorithm that is fast but wrong is useless. A loop invariant is a statement about the program state that is true before every iteration of a loop. Proving correctness with an invariant has three parts: initialization (it is true before the first iteration), maintenance (if it is true before an iteration, it stays true after), and termination (when the loop ends, the invariant gives a useful property).
For insertion sort the invariant is: at the start of the iteration for index i, the prefix items[:i] contains the original first i elements in sorted order. It holds at the start because a prefix of one element is trivially sorted. Each iteration inserts items[i] into its correct position in the sorted prefix, so the prefix grows and the invariant holds again. When the loop ends the prefix is the whole list, and so the whole list is sorted.
The program turns the invariant into an assert. This is a teaching technique: sorting the prefix on every iteration is far too expensive for production code, and Python removes assert statements when run with -O. The point is that stating the invariant clearly is what makes the correctness argument checkable.
Explore the dry run
def insertion_sort(values): items = list(values) for i in range(1, len(items)): assert items[:i] == sorted(items[:i]) key = items[i] j = i - 1 while j >= 0 and items[j] > key: items[j + 1] = items[j] j -= 1 items[j + 1] = key assert items == sorted(items) return items print(insertion_sort([5, 2, 4, 6, 1, 3]))print(insertion_sort([]))Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Invariant: before iteration i, the first i items are already in sorted order. | i = 1: [5] is sorted | — | |
| Larger items shift one place right to open a gap for the key. | key = 2: [5, 5, ...] | — | |
| The key lands in its sorted position, so the prefix of length i + 1 is sorted: maintenance. | [2, 5, 4, 6, 1, 3] | — | |
| Termination: the invariant now covers the whole list, so the result is sorted. | [2, 5, 4, 6, 1, 3] | — | |
| An empty list never enters the loop; the invariant holds trivially. | [2, 5, 4, 6, 1, 3] | [1, 2, 3, 4, 5, 6] [] |
Cost and common mistakes
Insertion sort is Θ(n²) in the worst case and Θ(n) for already sorted input, with O(1) extra space besides the copy. The assertions add O(n log n) per iteration and are for teaching only.
- An invariant must hold before the loop, after each iteration, and be strong enough to prove the final goal. A true but weak statement proves nothing.
- assert statements are removed under python -O, so they document and test the invariant but are not a runtime safety mechanism.
- Passing tests is not a proof of correctness. The invariant argument covers every input; tests cover only the inputs tried.
Try it yourself
State a loop invariant for a function that sums a list with a for loop and an accumulator total.
Reveal answer and reasoning
Before each iteration, total equals the sum of the items already visited. It is true initially (an empty sum is 0), preserved by adding the next item, and at the end total is the sum of all items.