Insertion Sort

Sorting

Stable

In-place

avg O(n²)

Insertion sort works the way most people sort playing cards: keep the cards in your hand sorted, pick up the next card, and slide it into the right spot. It is simple, stable, and surprisingly practical - on small or almost-sorted arrays it beats the famous O(n log n) algorithms, which is why real sorting libraries still use it under the hood.

Watch it sort

Press play - or drag the timeline and step through it yourself.

Pass 1Comparisons 0Swaps 0Step 1 / 186

18 values. The first one alone counts as sorted. Insert the rest one by one.

comparing shifting sorted so far done not inserted yet

Complexity

Best

O(n)

Input already in order

Average

O(n²)

Normal mixed input

Worst

O(n²)

Worst possible input

Space

O(1)

Extra memory used

Stable: yes - equal values keep their orderIn-place: yes - no copy of the array needed

Sorting cards in your hand

You are dealt cards one at a time. The cards already in your hand are sorted. Each new card, you scan from the right: is this card smaller than that one? Keep moving left until you find where it fits, then slide it in. You never re-sort the whole hand - you only find the right gap for the newest card. That is insertion sort, exactly.

How it works, step by step

Treat the first value as a sorted section of size one.
Pick up the next value (the "card").
Compare it with the values in the sorted section, moving right to left. Every value that is bigger shifts one step right to make room.
When you find a value that is not bigger (or reach the front), drop the card into the gap.
The sorted section is now one bigger. Repeat with the next value.
When every value has been inserted, the array is sorted.

The code, in JavaScript

The classic version: hold the current value in `key`, shift bigger values right, drop `key` into the gap.

javascript

function insertionSort(arr) {
  const a = [...arr];              // copy, so we don't change the input

  for (let i = 1; i < a.length; i++) {
    const key = a[i];              // the "card" we picked up
    let j = i - 1;

    // Shift everything bigger than key one step right.
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }

    a[j + 1] = key;                // drop the card into the gap
  }

  return a;
}

insertionSort([5, 1, 4, 2]);       // → [1, 2, 4, 5]

Dry run: sorting [5, 1, 4, 2]

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

Step	Pass	Array	What happened
1	1	[5, 1, 4, 2]	Pick up 1. Walk it left through the sorted part until it fits.
2	1	[5, 1, 4, 2]	5 > 1 - too big, shift 5 one step right.
3	1	[1, 5, 4, 2]	Moved 1 past 5.
4	2	[1, 5, 4, 2]	Pick up 4. Walk it left through the sorted part until it fits.
5	2	[1, 5, 4, 2]	5 > 4 - too big, shift 5 one step right.
6	2	[1, 4, 5, 2]	Moved 4 past 5.
7	2	[1, 4, 5, 2]	1 ≤ 4 - found the spot. 4 stays here.
8	3	[1, 4, 5, 2]	Pick up 2. Walk it left through the sorted part until it fits.
9	3	[1, 4, 5, 2]	5 > 2 - too big, shift 5 one step right.
10	3	[1, 4, 2, 5]	Moved 2 past 5.
11	3	[1, 4, 2, 5]	4 > 2 - too big, shift 4 one step right.
12	3	[1, 2, 4, 5]	Moved 2 past 4.
13	3	[1, 2, 4, 5]	1 ≤ 2 - found the spot. 2 stays here.

Good choice when…

The data is almost sorted - each value is near its final spot. Then insertion sort runs in nearly O(n), faster than merge or quick sort.
The array is small (up to ~20 items). Real libraries - including V8's TimSort - switch to insertion sort for small runs because its low overhead wins there.
Values arrive one at a time and you need the list sorted after every arrival (online sorting). Insertion sort is exactly that.
You need a stable, in-place sort in a few lines of code.

Bad choice when…

The input is large and shuffled. The shifts add up to O(n²) - 10,000 random items means about 25 million shifts.
The input tends to arrive in reverse order. That is the worst case: every card walks all the way to the front.
You are moving big objects in memory in a language where moves are costly - every shift copies an element. (Selection sort makes fewer moves.)

Common mistakes

The inner loop condition must be `a[j] > key`, not `>=`. With `>=`, equal values jump over each other and the sort is no longer stable - the one property insertion sort is loved for.
Do not re-scan from the left to find the spot. The whole trick is scanning from the right edge of the sorted part, which is what makes almost-sorted input nearly O(n).
Binary insertion reduces comparisons, not total time. The shifting is still O(n) per card. People quote it as an O(n log n) sort - it is not.
In JavaScript, shifting with `a[j + 1] = a[j]` in a loop is much faster than `splice` per step - `splice` re-shifts internally, doubling the work.

Insertion Sort vs. its closest relatives

Algorithm	Best	Average	Worst	Space	Stable
Insertion Sortthis page	O(n)	O(n²)	O(n²)	O(1)	yes
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	no
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	yes
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	no