Correctness with loop invariants
Prove that insertion sort is correct by checking an invariant before every iteration.
On this page
Loops, lists, and sorting.
- Prove that insertion sort is correct by checking an invariant before every iteration.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
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.
Code example
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] []
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
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] [] |
Behind the scenes
How Python processes this code
Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.
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.