Insertion Sort: Each Pass Inserts One Key

A sorted prefix grows by exactly one position on every pass

Insertion sort treats the first value as a sorted prefix, then inserts one unread value into that prefix on each outer pass. The unread suffix is not searched for its smallest value. For [5, 2a, 4, 6, 2b, 3], the first prefix is [5], and pass i = 1 inserts 2a before it, producing [2a, 5, 4, 6, 2b, 3].

On pass i = 2, key 4 moves between 2a and 5. On pass i = 3, key 6 stays where it is, but the sorted prefix still gains index 3. On pass i = 4, key 2b moves past 4, 5, and 6, stopping after 2a. The final pass inserts 3 between 2b and 4. Every pass consumes exactly one next value, whether that value moves several places or does not move at all.

Saving the key creates room to shift larger values right

During the pass that inserts 2b, the sorted prefix is [2a, 4, 5, 6]. The value 2b must be copied into key before any array position is overwritten. The scan starts at 6, moves 6 from index 3 to index 4, then moves 5 from index 2 to index 3, and moves 4 from index 1 to index 2.

Those shifts leave index 1 as a hole, but they do not lose the key because 2b is stored separately. The scan stops at 2a because 2a is equal to key 2b, not greater than it. Writing key into the hole produces [2a, 2b, 4, 5, 6, 3]. The equal values keep their original order because the comparison does not shift an equal value.

The loop conditions place the key without crossing the left edge

The outer index starts at 1 because index 0 alone is already a sorted prefix. At each pass, key saves array[i], and j starts at i - 1, the last index of the prefix. The inner loop continues only while j is valid and array[j] is larger than key.

for (int i = 1; i < n; i++) {
    int key = array[i];
    int j = i - 1;

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

    array[j + 1] = key;
}

The condition j >= 0 prevents the scan from reading before the array. The second condition, array[j] > key, limits shifts to values strictly larger than the key. Both conditions matter: the first protects the index, and the second identifies the correct insertion point while preserving the order of equal values. After the loop, j is either -1 or points to a value no greater than key, so array[j + 1] is the hole.

while (__________) {
    array[j + 1] = array[j];
    j--;
}

The performed shifts determine both the running time and the stable order

For this array, count a value comparison only when array[j] > key is evaluated, including the final false comparison that stops a pass. Do not count the j >= 0 check, and do not count assignments as comparisons. The five passes make 1, 2, 1, 4, and 4 value comparisons, for 12 total. They make 1, 1, 0, 3, and 3 shifts, for 8 total.

In the worst case, each new key is smaller than nearly every value in the sorted prefix, so the shifts and comparisons add up to O(n^2). In the best case, the array is already sorted, so each pass makes one value comparison and no shifts, giving O(n) time. The algorithm rearranges the array in place and stores only key and j, so its extra space is O(1).

The strict comparison array[j] > key is also what makes insertion sort stable. When key is 2b, the scan shifts 6, 5, and 4, then stops at equal 2a. The final array keeps 2a before 2b, matching their original order. Replacing > with >= would shift 2a and could reverse equal values.