In insertion sort, what does the sorted-prefix loop invariant actually guarantee at the start of each pass?
answer
- Two clauses, not one
- Which elements, and in what order
- Compare against a selection-based prefix
- Sorted so far, but not finished
- Guard the index before the comparison
basics
~20 sThe invariant says the first i elements are the ones that started there, now in sorted order. It does not say they are in final positions — a later, smaller element can land among them and push the rest right.
solid answer
~50 sAt the start of the pass that processes index `i`, the region `a[0..i-1]` holds exactly the elements that started there, now in sorted order. Two things follow. First, it is a **sorted prefix, not a finished prefix**: nothing has been compared against `a[i..n-1]`, so any later element may be smaller than everything in the prefix and displace all of it. That is the opposite of a selection-based sort, where the processed prefix already holds the final smallest elements. Second, initialisation is `i = 1` (a one-element region is trivially sorted), maintenance is the shifting inner loop, and termination at `i = n` gives the whole sequence sorted — which is the standard initialisation/maintenance/termination proof. The inner loop needs its own guard, `j >= 0`, evaluated *before* the element comparison, or the scan walks off the front of the region.
code
pseudocode · 7 linesfor i in 1..n-1
key = a[i]
j = i - 1
while j >= 0 and a[j] > key
a[j + 1] = a[j]
j = j - 1
a[j + 1] = keygo deeper
Be ready to say the already-processed part is sorted among itself, and to show with one example that a later element can still be inserted in front of it. Naming the loop that maintains it is enough at this level.
State the invariant in both clauses and walk initialisation, maintenance and termination out loud. An interviewer expects you to point at the index guard and explain why it must be checked before the element comparison.
Demonstrate that you use invariants as a review tool: given someone else's shifting loop, say what statement should hold and find the boundary where it fails. Be able to explain why this class of off-by-one survives random test data.
Own the argument that invariants are the cheapest correctness documentation a team can adopt — a one-line comment stating what must hold makes shifting and partitioning loops reviewable. Be ready to say where you would and would not require them.
## Stating the invariant precisely **Invariant.** At the start of the iteration that processes index `i`, the region `a[0..i-1]` consists of the elements originally in `a[0..i-1]`, rearranged into sorted order. Both halves matter. "Sorted order" is the obvious half. "The elements originally in `a[0..i-1]`" is the half candidates drop, and it is the half that makes the invariant useful — it says the algorithm has neither invented nor lost elements, and it pins down *which* elements the sorted region contains. ## What it does NOT say — the trap It does **not** say those `i` elements are in their final positions. The algorithm has never looked at `a[i..n-1]`. If the very next element is smaller than everything seen so far, it is inserted at the front and every element of the prefix moves one slot right. All that is preserved is sortedness *among the elements processed so far*. This is exactly where a selection-based sort differs: a sort that repeatedly extracts the minimum from the unprocessed region places each extracted element in its final resting position, so its prefix is both sorted *and* final. Insertion sort's prefix is sorted but provisional. If you can articulate that difference, you have understood what a loop invariant is for: it is the weakest statement that is both true at every step and strong enough to give you the result at termination. ## The three-part proof **Initialisation.** Before the first iteration `i = 1`, and `a[0..0]` is a single element, trivially sorted and trivially the element that started there. **Maintenance.** The pass saves `key = a[i]`, then shifts every element of the prefix that is strictly greater than `key` one position right, and writes `key` into the gap. Elements not greater than `key` are untouched and stay left of it; every shifted element is greater than `key` and ends up right of it. So `a[0..i]` is sorted and holds exactly the original `a[0..i]`, which is the invariant with `i` advanced by one. **Termination.** The loop ends with `i = n`. The invariant then reads: `a[0..n-1]` holds all the original elements in sorted order. That is the postcondition — the algorithm is correct. ## The boundary that actually breaks The inner loop has two exit conditions, and they are not symmetric: ``` while j >= 0 and a[j] > key ``` The range check must be evaluated **first** and must short-circuit. When `key` is smaller than every element in the prefix, `j` walks down to `-1`, and if the element comparison is evaluated before the range check, the code reads one slot before the start of the region. Writing `j > 0` instead of `j >= 0` is the other classic slip: the scan stops one element early, `a[0]` is never shifted, and the smallest element in the batch ends up in position 1 instead of position 0 — a bug that is invisible on most random inputs and shows up the moment the new element is the new minimum. Both errors are single characters, and both are what an interviewer is checking when they ask you to walk the boundary. ## Stability rides on the comparison operator The inner loop shifts while `a[j] > key` — **strictly** greater. When it meets an element equal to the key it stops, so the key settles *after* the equal elements that were already there, preserving their original relative order. That is what stability means: equal keys keep the relative order they had in the input. Change the test to `a[j] >= key` and equal elements get shifted past, the key lands before its equal predecessor, and the sort is no longer stable — while also doing strictly more work on duplicate-heavy input. Stability only has meaning when equal elements are distinguishable in some way you care about (a secondary field, an arrival order); if elements are indistinguishable, the property is unobservable. ## Why interviewers keep asking this Insertion sort is nobody's production sorting strategy at scale, but it is the smallest algorithm on which you can state a real loop invariant, prove it in three lines, and identify a genuine off-by-one. Every answer you give here transfers directly to binary search bounds, two-pointer scans and partition loops — which is precisely why the question outlives the algorithm.
- Why does the invariant have to mention which elements are in the prefix, not just that it is sorted?"Sorted" alone is satisfied by a region that has quietly lost or duplicated elements — overwriting the whole prefix with one repeated value keeps it sorted. Naming the multiset pins the algorithm to a permutation of the input, so termination gives you "all the original elements, in order" rather than merely "something ordered".
- Trace what happens when the key is smaller than every element in the sorted prefix.The inner loop shifts the entire prefix right one slot and `j` reaches `-1`. The range check `j >= 0` fires first and stops the scan; the key is then written to `a[j + 1]`, which is `a[0]`. The final write using `j + 1` rather than `j` is precisely what makes this boundary case land correctly.
- Does insertion sort's stability depend on anything other than the comparison operator?No — the shift-based movement is what makes stability achievable at all, and the strict `>` test is what realises it. Because elements move one slot at a time and never jump over an equal element, no pair of equal keys is ever swapped. Loosening the test to `>=` is the single change that destroys the property.
Filing papers into an open folder: the papers already filed are in order, but any paper still on the desk might belong at the very front and push the rest back.
saying these in an interview costs you the question
- Says the first i elements are already in final position
- States the invariant as merely 'the prefix is sorted'
- Puts the element comparison before the index guard
- Uses j > 0 as the inner-loop bound
- Thinks stability is unrelated to the comparison operator