Home/Sorting/Insertion sort
Search algorithmsCTRL K

Insertion sort

· insertion · slide into the sorted prefix
/sorting/insertion-sort
COMPARISONS
0
one per shift, plus one to stop
SHIFTS
0
equals the inversions fixed
KEY
—
value being inserted
PREFIX
1/ 24
sorted so far
GAP
—
where the key will land
keycomparingshiftedsorted prefix
n = 24 · seed 7 · 352 steps
step 0 / 351
Size24
insertion_sort.ts
1
function insertionSort(array: number[]) {
2
  for (let i = 1; i < array.length; i++) {
3
    const key = array[i];
4
    let j = i - 1;
5
    while (j >= 0 && array[j] > key) {
6
      array[j + 1] = array[j];
7
      j--;
8
    }
9
    array[j + 1] = key;
10
  }
11
}
CURRENT STEP
line 1

Start: array[0] = 27 alone is a sorted prefix of length 1.

// how it works

Understanding Insertion sort

insertion sort · the one the fast sorts fall back to
01

The idea

Insertion sort keeps a sorted prefix and grows it one element at a time. It lifts the next value out, shifts every larger element of the prefix one slot to the right, and drops the value into the gap. It is how most people sort a hand of cards.

The cost is the number of shifts, which equals the number of inversions in the input. Sorted input needs n − 1 comparisons and no shifts; reversed input needs n²/2 of each. That adaptivity is why quick sort and Tim sort hand small or nearly sorted runs to it.

02

The four stages

1
liftkey ← array[i]
2
comparearray[j] against the key, right to left
3
shiftlarger values move one slot right
4
dropkey lands in the gap, prefix grows
03

Complexity

best
O(n)sorted input: one comparison per element
average
O(n²)n²/4 comparisons and shifts
worst
O(n²)reversed input
space
O(1)in place, one key held aside
04

Versus its siblings

COMPARISONS AT N = 1 000 · NEARLY SORTED
selection
499,500
quick
13,900
merge
8,700
bubble
2,000
insertion
1,100
input with 5% of the pairs out of order · adaptive sorts win here
05

Pseudocode

INSERTIONSORT(array)
  for i ← 1 to n − 1
    key ← array[i]; j ← i − 1
    while j ≥ 0 and array[j] > key
      array[j + 1] ← array[j]; j ← j − 1
    array[j + 1] ← key
06

When to use

Small arrays, roughly under 32 elements: it is what std::sort, Tim sort and pdqsort switch to at the bottom of their recursion.
Data that arrives nearly sorted, or an online setting where elements come one at a time and the list must stay sorted.
07

Pitfalls

Quadratic on random input: past a few dozen elements any O(n log n) sort wins.
Shifting one slot at a time is the cost; binary insertion cuts the comparisons but not the shifts.
On a linked list the shifts vanish, but so does the binary search.
08

History

John Mauchly described insertion sort, with a binary search for the slot, in a 1946 lecture at the Moore School, one of the first published sorting methods for a computer. Its adaptivity made it the finishing step of every practical hybrid sort since, from Sedgewick's quick sort variants to Tim Peters' Tim sort in 2002.

Back to Sorting