Insertion Sort

Insertion sort builds a sorted part on the left one value at a time: it picks up the next value and slides it left until it sits in the right place — like sorting a hand of cards.

Start

5
3
8
2
9
1
4
  • Card being inserted
  • Comparing
  • Moving
  • Sorted part

Insertion sort grows a sorted part on the left, one card at a time — like sorting a hand of cards.

Step 1 / 41
Comparisons
0
Shifts
0
for i from 1 to n − 1:
  key = a[i]
  j = i − 1
  while j ≥ 0 and a[j] > key:
    a[j + 1] = a[j]   // shift right
    j = j − 1
  a[j + 1] = key

What's happening?

  1. The first value on its own counts as sorted.
  2. Each next value is "picked up" and compared with the sorted values to its left; bigger ones shift right to make room.
  3. When a smaller (or equal) value is reached, the picked-up value drops into the gap.

Complexity

Time
O(n²) worst and average · O(n) when already nearly sorted
Space
O(1) — sorts in place

Where you'll meet it

Small or nearly-sorted data. Real libraries (Java's and Python's sorts, TimSort) switch to insertion sort for short runs because it is so fast there.

Common mistake

Assuming it is always slow. On nearly sorted input it does almost no work — often beating "faster" algorithms.

FAQ

Is insertion sort stable?

Yes. Equal values never pass each other, so their original order is kept.

Why is it fast on nearly sorted data?

Each value only moves as far as it is out of place. If nothing is far out of place, there is little to shift.

Insertion sort vs bubble sort?

Both are O(n²), but insertion sort usually does far fewer moves and is preferred in practice.