Insertion Sort

The idea

Think about how you sort a hand of playing cards. You pick up cards one at a time, and each new card gets inserted into the correct place among the cards you’re already holding. The cards in your hand are always sorted.

Insertion sort does exactly this:

1. Treat the first element as a sorted list of length 1.
2. Take the next element — the key.
3. Shift every bigger element in the sorted part one place right.
4. Drop the key into the gap.
5. Repeat until every element has been inserted.

In the 3D model, the key steps forward out of the row, the bigger bars slide right one by one, and the key drops into the hole.

Step by step example

Sorting [5, 2, 4, 6, 1, 3]:

Code

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]          # shift right
            j -= 1
        a[j + 1] = key               # drop into the gap
    return a

print(insertion_sort([5, 2, 4, 6, 1, 3]))   # [1, 2, 3, 4, 5, 6]

#include <iostream>
#include <vector>
using namespace std;

void insertionSort(vector<int>& a) {
    for (int i = 1; i < (int)a.size(); i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

int main() {
    vector<int> a = {5, 2, 4, 6, 1, 3};
    insertionSort(a);
    for (int x : a) cout << x << " ";   // 1 2 3 4 5 6
}

Analysis

• Best case — O(n): the array is already sorted, so each key is compared once and never moves.
• Worst case — O(n²): the array is reversed, so key number i shifts past all i sorted elements: 1 + 2 + … + (n−1) = n(n−1)/2 moves.
• Space — O(1): it sorts in place.

It is stable, in-place and adaptive (it gets faster the more sorted the input already is) and online — it can sort data as it arrives.

Insertion sort vs bubble sort vs selection sort

Where is it used?

Insertion sort is the go-to algorithm for small or nearly sorted arrays. Real libraries take advantage of this: Timsort (Python’s sorted, Java’s object sort) and introsort (C++ std::sort) both switch to insertion sort for pieces smaller than about 16–64 elements.

Common mistakes

• Writing a[j] >= key — it still sorts, but it is no longer stable.
• Forgetting j >= 0 in the loop condition (index −1 crash).
• Placing the key at a[j] instead of a[j + 1].