Insertion sort · Lessons

Insertion sort: shift the larger elements right, insert into the hole

Student can produce insertion sort using the shift-and-insert idiom (save current, shift larger elements right with a backward inner loop, drop current into the hole), distinguish the algorithm's outer-loop invariant from selection sort's, and identify the O(n) best case and O(n²) worst case.

Insertion sort sorts in place by walking left-to-right and inserting each element into its correct position among the elements already processed. Where selection sort finds the minimum of the suffix and swaps once per pass, insertion sort takes the next unprocessed element and slides it down through the sorted prefix until it lands in the right place.

public static void insertionSort(final int[] xs) {
    for (int i = 1; i < xs.length; i++) {
        final int current = xs[i];          // save the value to insert
        int j = i - 1;
        while (j >= 0 && xs[j] > current) { // shift larger elements right
            xs[j + 1] = xs[j];
            j--;
        }
        xs[j + 1] = current;                // drop current into the hole
    }
}

Three structural commitments distinguish this from selection sort:

1. The outer loop's i is "the next element to insert." i starts at 1 because xs[0] is trivially a sorted prefix of length 1. At the start of iteration i, the prefix xs[0..i-1] is sorted; at the end, the prefix xs[0..i] is sorted. 2. **The inner loop walks backward through the sorted prefix. Each comparison xs[j] > current checks whether the element at position j should be shifted right to make room for current. The loop continues while the prefix still has larger elements; it stops when j runs off the left edge (j < 0) or when xs[j] is no longer larger than current. 3. The element being inserted is saved in current before the shifting starts.** Without the save, the first shift xs[j+1] = xs[j] would clobber xs[i] (the value to insert): the same destructive-write problem as the swap that skips its temporary variable.

Why no swap

A naive presentation of insertion sort uses repeated swaps: slide current left one position at a time by swapping with its neighbor. That works and is sometimes pedagogically clearer, but it costs three assignments per shift (the temp-swap) versus one (xs[j+1] = xs[j]). For 1 000 000 elements the difference is real. The CSCD 210 lecture style teaches the shift-and-insert form because it is the form java.util.Arrays.sort uses internally (in its small-subarray path).

Best-case vs worst-case

Insertion sort is the rare O(n²) algorithm with a meaningful best case:

Best case (already sorted): the inner loop's condition xs[j] > current is false on the very first check, so it makes one comparison and no shifts. Total work: n - 1 comparisons, O(n).
Worst case (reverse sorted): every new element has to shift past every prior element. Total work: n(n-1)/2, O(n²).

This is why insertion sort is the right choice for nearly-sorted data, and why hybrid sorts like Timsort fall back to insertion sort for small or partially-sorted subarrays.

In other languages

C: identical algorithm; identical shift-and-insert idiom.
Python: sorted(xs) uses Timsort which falls back to insertion sort for small subarrays. The pattern is internal.
Rust: slice::sort uses pattern-defeating quicksort with insertion-sort fallback.

Tracing insertion sort pass by pass

Student can trace insertion sort on a small input by producing a table that lists, for each outer-loop pass: the value of i, the value of current, and the array state after the insertion completes; and identify which pass is the most expensive (in shifts) for a given input.

Insertion sort's trace looks superficially like selection sort's (one row per outer-loop pass, showing the array after each), but the invariant in each row differs. The sorted prefix in insertion sort is the values seen so far, in their sorted order, not "the smallest values in their final positions."

The trace format

For int[] xs = {5, 2, 8, 1, 9, 3}:

| Pass | i | current | Array after the insertion | |------|---:|---:|---------------------------| | (initial) |: |: | {5, 2, 8, 1, 9, 3} | | 1 | 1 | 2 | {2, 5, 8, 1, 9, 3} | | 2 | 2 | 8 | {2, 5, 8, 1, 9, 3} | | 3 | 3 | 1 | {1, 2, 5, 8, 9, 3} | | 4 | 4 | 9 | {1, 2, 5, 8, 9, 3} | | 5 | 5 | 3 | {1, 2, 3, 5, 8, 9} |

Five things to notice:

1. The outer loop starts at i = 1. Slot 0 alone is trivially sorted; pass 1 is the first real insertion. A 6-element array has 5 outer-loop passes (one less than its length). 2. Pass 2 (current = 8) is a no-op for the array. 8 is larger than every element in xs[0..1] (which is {2, 5} after pass 1), so the inner loop terminates immediately and current is written back to its original slot. The array is unchanged. 3. Pass 3 (current = 1) is the most expensive pass. 1 is smaller than every element in xs[0..2] ({2, 5, 8}); the inner loop shifts three elements right before placing current at index 0. 4. **The sorted prefix at the end of pass k is the first k+1 values of the original array, sorted. After pass 3, the prefix is {1, 2, 5, 8}: the four values {5, 2, 8, 1} from the original, sorted. The remaining suffix {9, 3} is still the original. 5. The total number of inner-loop shifts equals the number of inversions in the original array.** This is what makes insertion sort efficient on nearly-sorted inputs.

What changes between selection and insertion traces

Same row count (n - 1 passes for an n-element array). Same "array after pass" column. Different columns:

| Algorithm | Per-pass columns | |-----------|------------------| | Selection | start, minIdx (after inner loop) | | Insertion | i, current (the value being inserted) |

The midterm 2 rubric expects the column set that matches the algorithm. Mixing them (writing minIdx for insertion or current for selection) costs points.

The trace as design

Two complementary algorithm-design lenses become visible in the comparison:

Selection sort answers "where does the smallest unplaced element belong?" then places it. Each pass places one element finally.
Insertion sort answers "where does the next-unprocessed element belong in the prefix?" then slots it in. Each pass extends the sorted prefix by one position but does not guarantee the final position of any element until the algorithm completes.

The trace tables make the contrast concrete. CSCD 210 lecture week6-lec4 puts the two traces side-by-side for the same input.

In other languages

Python: Timsort's "natural runs" detection is implemented exactly with insertion-sort-style invariants on the small-run path; the trace technique extends.
Spreadsheet: the trace fits naturally: each row is one outer pass; each column is i, current, and the array slots.