Insertion Sort Visualization

Insertion sort is how most people sort a hand of playing cards without thinking about it: pick up the next card, slide it left past every bigger card, and drop it where it fits. The left portion of your hand is always sorted; it just grows by one card at a time. Watch the animation below and you’ll see that same behavior: values shifting right in little cascades as each new bar burrows leftward into the sorted region.

How it works

The algorithm walks the array once, left to right. For each element (the key in the code below), it scans backward through the already-sorted prefix, shifting larger values one slot to the right until it finds where the key belongs, then writes the key there. Unlike bubble or selection sort, nothing is “locked in” early. A future key can still land anywhere in the prefix, which is why the bars only turn green in one final sweep at the end.

The cost depends entirely on how far each key has to travel. On random input each key shifts halfway back on average, about n²/4 operations, solidly O(n²). But on nearly-sorted input, insertion sort flies: each key is already close to home, the backward scan exits after one comparison, and the whole run is O(n). Shuffle the bars a few times and compare it with selection sort, which does identical work no matter what. This adaptivity is why insertion sort is the only quadratic algorithm on this site that real libraries still run every day.

When interviewers ask about it

Insertion sort appears in interviews as the “when would a quadratic sort be the right choice?” question. The strong answers: small arrays (for a dozen elements, its tiny constant factor beats clever algorithms, which is why standard-library sorts like Timsort and introsort switch to insertion sort for small partitions), nearly-sorted data (O(n) adaptive behavior), and streaming input, since it can keep a running list sorted as elements arrive. It’s also stable and in-place, so it never destroys duplicate order. If an interviewer asks you to improve merge sort or quicksort, “cut over to insertion sort below ~16 elements” is a classic optimization worth naming.

Insertion sort (including implementing it from scratch) is taught in Day 6: Advanced Sorting Algorithms, Insertion Sort and Merge Sort, building on the sorting fundamentals from Day 5.

Complexity at a glance

The exact code you are watching

This is the real generator that drives the animation above, read from sort-algorithms.js at build time, so the code and the visualization can never drift apart. Each yield is one visual step.

 1function* insertionSort(a) {
 2  for (let i = 1; i < a.length; i += 1) {
 3    const key = a[i];
 4    let j = i - 1;
 5    while (j >= 0) {
 6      yield { type: 'compare', i: j, j: j + 1 };
 7      if (a[j] <= key) {
 8        break;
 9      }
10      a[j + 1] = a[j];
11      yield { type: 'overwrite', i: j + 1, value: a[j + 1] };
12      j -= 1;
13    }
14    a[j + 1] = key;
15    yield { type: 'overwrite', i: j + 1, value: key };
16  }
17  for (let i = 0; i < a.length; i += 1) {
18    yield { type: 'markSorted', i: i };
19  }
20}