The Insertion Sort Algorithm

Bubble sort sorts by repeatedly scanning the whole list and swapping neighbors. Insertion sort takes a different approach: it keeps a sorted section at the front of the list and grows it one element at a time, inserting each new value exactly where it belongs — the way most people sort a hand of playing cards.

The idea

Insertion sort treats the list as split into two parts: a sorted prefix at the front, and everything else. Initially the sorted prefix is just the first element — a single element is trivially "sorted".

For each following element, called the key, insertion sort shifts it into the sorted prefix: it compares the key against the prefix from right to left, moving each larger element one position to the right, until it finds where the key belongs. That gap left behind by shifting is exactly where the key is placed. Once that is done, the sorted prefix has grown by one, and the process repeats with the next element.

Implementation

#include "plot.hpp"
#include <stdlib.h>

const int N = 20;
int values[N];
int i = 1;     // index of the element currently being inserted
int k = -2;    // -2 = pick a new key, -1..i-1 = shifting comparison pointer
int key = 0;
bool done = false;
int tick = 0;

void setup() {
    PlotCanvas(640, 480);

    for (int n = 0; n < N; n++) {
        values[n] = n + 1;
    }

    srand(1);
    for (int n = N - 1; n > 0; n--) {
        int r = rand() % (n + 1);
        int tmp = values[n];
        values[n] = values[r];
        values[r] = tmp;
    }
}

void frame() {
    // Slow the animation down: one step every few calls to frame() instead
    // of one per call, so individual shifts stay visible.
    if (!done && ++tick >= 4) {
        tick = 0;

        if (k == -2) {
            if (i >= N) {
                done = true;
            } else {
                key = values[i];
                k = i - 1;
            }
        } else if (k >= 0 && values[k] > key) {
            values[k + 1] = values[k];
            k--;
        } else {
            values[k + 1] = key;
            i++;
            k = -2;
        }
    }

    PlotBackground(250, 250, 250);

    int activeIndex = (k == -2) ? i : (k + 1);
    int barWidth = plot_width / N;

    for (int idx = 0; idx < N; idx++) {
        if (!done && idx == activeIndex) {
            PlotColor(220, 60, 60);   // the key currently being inserted
        } else if (idx < i) {
            PlotColor(70, 170, 90);   // sorted prefix
        } else {
            PlotColor(30, 100, 200);  // not yet reached
        }

        int height = values[idx] * (plot_height - 20) / N;
        int x0 = idx * barWidth + 1;
        int x1 = x0 + barWidth - 2;
        int y0 = plot_height - height;
        int y1 = plot_height;
        PlotFilledRectangle(x0, y0, x1, y1);
    }
}

i marks how far the sorted prefix reaches; k walks backward through it comparing against key, shifting elements right (values[k + 1] = values[k]) as long as they are bigger. When k runs out of bigger elements to shift, key is written into the gap and i advances. As with the bubble sort sample, frame() only performs one such step every few calls so the individual shifts stay visible instead of finishing instantly. Bar colors mark the same three states as before, just with a different meaning:

• green — the sorted prefix
• red — the key currently being inserted
• blue — not reached yet

Walking through an example

For [5, 1, 4, 2, 8], the sorted prefix starts as just [5]. Inserting 1:

The prefix is now [1, 5]. Inserting 4 next only needs one shift (5 moves right, 4 lands between 1 and 5); inserting 2 needs two shifts past 5 and 4; 8 needs none, since it is already larger than everything in the prefix. After all four insertions the list is sorted.

Why it is sometimes still used

Insertion sort is O(n²) in the worst case, just like bubble sort — no better asymptotically. But two properties keep it in real use:

• Best case O(n): if the list is already sorted, or nearly so, every key only needs one comparison before it turns out no shift is necessary. Bubble sort's naive version does not have this property; insertion sort gets it for free from the comparison direction it scans in.
• Good on small inputs: for short arrays (roughly under 10–20 elements, depending on the system), insertion sort's low overhead per comparison beats the setup cost of recursive divide-and-conquer sorts. This is why production sort implementations — Timsort, introsort, and most std::sort implementations — switch to insertion sort once a recursive partition shrinks below a small size threshold, instead of recursing all the way down.

It is also a stable sort: elements that compare equal keep their original relative order, since a key is only ever shifted past strictly smaller elements. Bubble sort shares this property; not every sorting algorithm does.

Conclusion

Where bubble sort repeatedly re-scans the whole list, insertion sort commits to a growing sorted region and does exactly the work needed to place each new element into it. That difference — asymptotically irrelevant, since both are O(n²) — turns out to matter a lot in practice, which is why insertion sort, unlike bubble sort, still shows up inside the standard sorting algorithms used today.