Insertion sort grows a sorted prefix without freezing its values

A sorted prefix grows even though its values can still move

Insertion sort treats the first element as a sorted prefix, then inserts each next value into the correct position inside that prefix. For [7, 4a, 5, 4b], the prefix starts as [7]. After processing 4a, it is [4a, 7]. After processing 5, it is [4a, 5, 7]. After processing 4b, it is [4a, 4b, 5, 7]. Each completed outer iteration extends the prefix by one position.

Sorted means the values are in ascending order relative to one another. It does not mean every value has reached the index it will occupy at the end. When 5 is inserted, 7 moves from index 1 to index 2. When 4b is inserted, both 5 and 7 move right again. The loop invariant is that before each outer iteration, the prefix before the current index is sorted.

Initial:       [7 | 4a, 5, 4b]
After i = 1:   [4a, 7 | 5, 4b]
After i = 2:   [4a, 5, 7 | 4b]
After i = 3:   [4a, 4b, 5, 7 |]

Saving the key before shifting prevents data from being overwritten

The value at the current index is the key to insert. Save it before moving any prefix value, because each shift writes into a position that may still be needed. Start with key = 4b from index 3 and the sorted prefix [4a, 5, 7]. The key is held separately, leaving a hole where it was. Then compare values from right to left.

int key = a[i];
int j = i - 1;

while (j >= 0 && a[j] > key) {
    a[j + 1] = a[j];
    j--;
}

a[j + 1] = key;

For key 4b, j starts at index 2, where the value is 7. Since 7 is greater than 4b, copy 7 to index 3 and move j to 1. Then copy 5 to index 2 and move j to 0. The comparison with 4a is false because the values are equal, so the hole is index j + 1, which is index 1. Writing the saved key there gives [4a, 4b, 5, 7].

The boundary test must run before the array access

When inserting 4a at i = 1, j starts at 0. The comparison 7 > 4a is true, so 7 shifts right and j becomes -1. At that point there is no prefix value left to inspect. The condition must test j >= 0 before evaluating a[j] > key, because the first test prevents the second test from reading outside the array.

while (j >= 0 && a[j] > key) {
    a[j + 1] = a[j];
    j--;
}

while (________) {
    a[j + 1] = a[j];
    j--;
}

The distance each key travels determines the work

For [7, 4a, 5, 4b], inserting 4a shifts 7 once. Inserting 5 shifts 7 once. Inserting 4b shifts 7 and 5, twice. The complete trace therefore makes 4 right shifts. The value comparisons are 7 > 4a, 7 > 5, 4a > 5, 7 > 4b, 5 > 4b, and 4a > 4b, for 6 comparisons.

A key can travel zero positions when it already belongs at the end of the prefix, so an already ascending array takes O(n) work: each outer iteration makes only its boundary comparison. In the worst case, each key travels across most of the prefix, giving 1 + 2 + ... + (n - 1) shifts and comparisons, which is O(n^2). The algorithm uses O(1) auxiliary space because it stores only the key, an index, and a constant number of temporary values.

The strict comparison a[j] > key also controls equal values. Since 4a > 4b is false when their values are equal, 4b is inserted after 4a. Equal values keep their original relative order, so this version of insertion sort is stable.