Insertion Sort

Take each value and slide it backward over larger ones until it sits in its place in the sorted prefix.

Insertion sort works the way you sort a hand of playing cards: pick up the next card and slide it backward over the cards already in your hand until it lands in the right slot. The front of the list is a sorted prefix that grows by one each step. It's the go-to sort for small or nearly-ordered lists.

Slide the key into place

1Treat the first element as a sorted prefix of length 1.
2Take the next value as the key.
3Shift every value in the prefix that's larger than the key one slot to the right.
4Drop the key into the gap that opens up — the prefix is now one longer.
5Repeat until every element has been inserted.

Adaptive: faster the closer to sorted

If the key is already ≥ the last prefix value, no shifting happens and the inner loop exits at once. On nearly-ordered data almost every insertion is instant, so the running time drops toward O(n) — the best behaviour of any simple sort.

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) { // slide larger values right
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key; // drop the key into the gap
  }
  return arr;
}

Stable and online

The shift loop stops at the *first* value not greater than the key, so equal values never jump past each other — insertion sort is stable. It's also online: it can keep a list sorted as new items arrive, without restarting.

OperationTimeSpace

Best (nearly sorted) · almost no shiftingO(n)O(1)

Average / worst · reversed input shifts everythingO(n²)O(1)

Check yourself

Why is insertion sort called adaptive?