Insertion Sort

Pick up a hand of playing cards, one at a time, and watch what your own hands do. You hold a small tidy fan of the cards you've already sorted, and each time you pick up a new card you slide it left along the fan until it sits in the right spot — nudging the bigger cards aside to make room. You never sort the whole hand at once; you grow a sorted run and insert each new card into it. That everyday habit is an algorithm, and it has a name: insertion sort.

The idea in one sentence:

Keep a sorted section at the front of the list (it starts as just the first item, which is trivially "sorted").
Take the next item after it and insert it into its correct place inside the sorted section, shifting every larger item one place to the right to open a gap.
Repeat until every item has been inserted — then the whole list is sorted.

Watch it happen, pass by pass

Here is the list [5, 2, 4, 1, 3] being sorted. Read the diagram from the top down: each row is the list after one more item has been inserted. The shaded cells on the left are the sorted section, and it grows by one every pass; the highlighted cell is the item we just slotted into place. Step through it:

Notice the sorted section only ever grows, and every new item burrows leftwards just far enough to land in order. By the last row the sorted section is the whole list.

The algorithm in code

The outer loop walks along the list starting at index 1 (index 0 is the one-item sorted section we begin with). For each item we save it as current, then the inner while loop shuffles every larger item one place to the right until the gap is in the right spot — and we drop current into that gap. Press Run and watch the list after each insertion:

Each printed line matches one row of the diagram above. Two things are worth naming. The algorithm sorts in place — it rearranges the one list, never building a second — and the inner loop stops early the moment it meets an item that is not bigger than current, because everything to its left is already sorted and therefore smaller. That early stop is the secret of the next section.

How does it compare with bubble sort?

You've already met bubble sort, which repeatedly walks the whole list swapping neighbours that are out of order. Both algorithms are simple and both take on the order of n^2 steps in the worst case for a list of n items. But insertion sort usually does the same job with fewer moves, for two reasons:

each item is shifted straight towards its home, rather than bubbled one swap at a time across many passes;
the inner loop stops as soon as an item is already in place, so it needn't scan the rest of the sorted section.

This makes insertion sort a star on nearly-sorted data. If a list is already almost in order, each new item barely moves — often not at all — so a run of n items costs only about n comparisons. That's why insertion sort is the method of choice for keeping a list tidy as items trickle in one at a time (adding a late score to an already-sorted leaderboard, say), and why real-world sorting libraries quietly switch to it for small or almost-sorted stretches.

Insertion sort is what's called an online algorithm: it can start sorting before it has seen every item, because at each moment it keeps a correctly sorted section of everything it has seen. Deal the cards one by one and your left hand is always in order, even mid-deal. Bubble sort can't do that — it needs the whole list in front of it before it can even begin its first sweep. It's a small idea with a big payoff: insertion sort is perfect whenever data arrives as a live stream rather than all at once.

The classic insertion-sort bug is overwriting the value you are trying to insert. When you shift a bigger item to the right, you copy it on top of the slot where the next item lives. If you haven't first saved the item you're inserting, that very first shift destroys it — and you end up duplicating a value and losing another:

// BUG: no temp variable — the first shift clobbers list[i]! for (let i = 1; i < list.length; i++) { let j = i - 1; while (j >= 0 && list[j] > list[i]) { list[j + 1] = list[j]; // this overwrites list[i] the moment j + 1 === i j = j - 1; // ...and now list[i] is gone forever } list[j + 1] = list[i]; // too late — list[i] is no longer the original }

The fix is the one habit the correct code above follows: copy the current item into a temporary variable before you shift anything (const current = list[i];), and always move items right before you drop the current one in. Save it, then shift, then place. In short: never shift over a value you still need.