Insertion Sort

Idea

Insertion Sort inserts each element into the already-sorted prefix, repeating until all elements are ordered.

The mental model is the one you use when you sort a hand of playing cards: you hold a sorted group in one hand and pick up one card at a time from the other, finding where it belongs in the group and putting it there. The sorted prefix grows by one element per pass, and the invariant — “everything before index $i$ is sorted” — holds at the top of every pass.

Algorithm

1. From the 2nd element onward, compare backward with the sorted part and insert at the right spot.
2. Repeat until all elements are placed.

Pseudo-code:

for i = 1 to n-1:
    key = A[i]
    j = i-1
    while j >= 0 and A[j] > key:
        A[j+1] = A[j]
        j--
    A[j+1] = key

Notice that the element is not “put in place” with a single assignment. It is carried to the left while larger elements slide right, and dropped into the gap that opens up. That is why the cost of one pass is proportional to how far the element has to travel, not to where it started.

Implementation

void InsertSort(int A[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = A[i];           // the element to insert
        j = i - 1;
        while (j >= 0 && A[j] > key) {
            A[j + 1] = A[j];  // shift the larger element right
            j--;
        }
        A[j + 1] = key;       // drop it into the gap
    }
}

Two details in this short routine are worth naming. The comparison uses > and not >=: with >=, elements that compare equal would be swapped and the sort would no longer be stable. And key is saved before the shifting loop, because the shifting overwrites A[i] — the element would be destroyed on the first iteration without a temporary copy.

Binary insertion sort

The comparisons of direct insertion sort can be optimised with a binary search: the prefix is already sorted, so the insertion position can be located by binary search rather than by walking backward. The number of comparisons drops from $O(n)$ per pass to $O(\log n)$, while the number of moves stays the same — the elements still have to slide.

void BinaryInsertSort(int A[], int n) {
    int i, j, low, high, mid, key;
    for (i = 1; i < n; i++) {
        key = A[i];
        low = 0; high = i - 1;
        while (low <= high) {          // binary search for the insertion point
            mid = (low + high) / 2;
            if (A[mid] > key) high = mid - 1;
            else low = mid + 1;
        }
        for (j = i - 1; j >= low; j--)  // shift the tail of the prefix right
            A[j + 1] = A[j];
        A[low] = key;
    }
}

The gain is real but bounded, and it is worth knowing why. Comparisons happen in registers and are cheap; moves happen in memory and are not. Since the moves are unchanged, binary insertion sort improves the constant factor of the comparison-heavy part without changing the overall order of growth. It also has to be careful about which of several equal elements it picks, or stability is lost — the A[mid] > key test above places the new element after equal ones, which is the stable choice.

Complexity

• Best: $O(n)$ (already sorted)
• Worst/avg: $O(n^2)$
• Space: $O(1)$
• Stability: stable

The best case is the interesting one. If the input is already sorted, the inner while loop never executes, and each pass costs a single comparison — $O(n)$ overall. This is a property insertion sort shares with merge sort and quick sort, and it is the reason insertion sort is not a bad choice for nearly sorted data.

Exercises

Exercise 1

Insert-sort $A = [5, 2, 4, 6, 1, 3]$ and show each pass.

Exercise 2

What are the time and space complexities of insertion sort?