SortingAlgorithmaka linear insertion sort

Insertion Sort

Build a sorted prefix by inserting each new element into its correct place among the ones before it.

▶ VisualizePattern: Two PointersPractice (2)
Progress

Overview

Insertion sort takes elements one at a time and inserts each into the already-sorted prefix by shifting larger elements one slot right. It is stable, in-place, online (can sort a stream as it arrives), and strongly adaptive: the running time is O(n + I) where I is the number of inversions, so nearly sorted input sorts in near-linear time.

It is the fastest sort in practice for small arrays (roughly n ≤ 16–32) because the inner loop is a tight shift with excellent cache and branch behaviour. Every serious library sort — TimSort in Python and Java, introsort in C++ std::sort, pdqsort in Rust and Go — switches to insertion sort for small subranges.

comparisonO(n²)stablein-placeadaptiveonlinesmall arrays

Intuition

A mental model before the formal terms.

Sorting playing cards in your hand: pick up the next card from the table and slide it leftwards past any bigger cards until it sits between a smaller card and a bigger one. The cards already in your hand are always in order.

How it works

  1. For i = 1 … n - 1, take key = a[i]; everything in a[0..i-1] is already sorted.
  2. Set j = i - 1. While j >= 0 and a[j] > key, shift a[j] to a[j + 1] and decrement j.
  3. Place key at a[j + 1].
  4. Optionally use Binary Search to find the insertion point in O(log n) comparisons — the shifts remain O(n).

Why it works

Invariant: before step i, a[0..i-1] is a sorted permutation of the original first i elements. The shift loop stops at the first a[j] ≤ key, so all elements right of j are > key and moved right by one; inserting key at j + 1 keeps the prefix sorted.

Using a[j] > key (strict) means equal elements are never moved past key, giving stability.

Each shift removes exactly one inversion, so total shifts equal the inversion count I, giving O(n + I).

Recognition

How to tell a problem wants this.

  • Input is nearly sorted or has few inversions ("each element is at most k positions from its sorted place").
  • Elements arrive online and the collection must stay sorted after each arrival.
  • Small n (< 32), or the base case of a recursive sort.
  • A linked list must be sorted in place with O(1) extra space.
“sorted array” → Two Pointers

Interactive visualization

Play, step, change the input. ← → and space work too.

29
0
10
1
14
2
37
3
13
4
5
5
42
6
21
7
1/47Start with 8 elements. The prefix a[0..0] of length one is trivially sorted; each round inserts the next element into it.
Key being insertedComparingShifted rightSorted prefix
PseudocodeLearn Insertion Sort →
1for i in 1 .. n-1:
2  key = a[i]
3  j = i - 1
4  while j >= 0 and a[j] > key:
5    a[j+1] = a[j]
6    j = j - 1
7  a[j+1] = key
Complexity
best O(n)
avg O(n²)
worst O(n²)
space O(1)
Speed

Pseudocode

1for i from 1 to n - 1:
2  key = a[i]; j = i - 1
3  while j >= 0 and a[j] > key:
4    a[j + 1] = a[j]; j -= 1
5  a[j + 1] = key

Implementations

1def insertion_sort(a: list[int]) -> None:
21 · Walk each element after the first
3    for i in range(1, len(a)):
42 · Take the key out
5        key = a[i]
6        j = i - 1
73 · Shift larger elements one slot right
8        while j >= 0 and a[j] > key:  # strict '>' keeps equal keys in order
9            a[j + 1] = a[j]
10            j -= 1
114 · Drop the key into the gap
12        a[j + 1] = key
Walkthrough
  1. range(1, len(a)) is empty for lists of length 0 or 1, so no guard is needed.
  2. key = a[i] copies the reference before the slot is overwritten.
  3. while j >= 0 and a[j] > key — and short-circuits; without the guard a[-1] would silently read the last element.
  4. Each shift is one list write; the final assignment places the key.
Complexity (this implementation)
time O(n + I); O(n) best, O(n²) worst · space O(1)

Python indexing is slow; bisect.insort does binary search + list.insert (memmove in C) and is much faster despite the same O(n) shift.

Language notes
  • bisect.insort(a, x) is the stdlib "insert into sorted list" and keeps stability (inserts after equal keys).
  • Negative indices wrap in Python: forgetting j >= 0 reads a[-1] instead of raising.
  • CPython's TimSort uses binary insertion sort for runs shorter than minrun.
Common mistakes in this language
  • Dropping j >= 0 — Python wraps to a[-1] and the sort silently corrupts.
  • Using >= which breaks stability.
  • Using a.insert(j, key) per element while also shifting — O(n) each and double work.
Language differences that matter here
  • Reading index -1: C++ is undefined behaviour, JS/TS return undefined (comparison silently false), Python wraps to the last element — the j >= 0 guard must come first in every language.
  • Library insertion helpers: C++ std::upper_bound + std::rotate, Python bisect.insort; JS/TS have none (splice is O(n) with allocation).
  • Every major library sort (introsort in std::sort, TimSort in Python and V8) falls back to insertion sort for short ranges.
  • JS/TS default sort() is lexicographic; the insertion sort above compares numerically.

Complexity

Best
O(n)
Average
O(n²)
Worst
O(n²)
Space
O(1)

Exactly O(n + I) where I = number of inversions. Stable, in-place, adaptive, online.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Small arrays (n ≤ 32) and as the base case of merge/quick/introsort.
  • Nearly sorted data or data with few inversions.
  • Online insertion into a small sorted buffer.
  • Sorting linked lists in place with a stable result.
Avoid it when
  • Large random inputs — O(n²) shifts; use Merge Sort, Quick Sort, or Heap Sort.
  • When the number of comparisons is the bottleneck on large n (binary insertion helps comparisons but not shifts).

Alternatives

Shell SortMerge SortTimSortBubble SortSelection Sort

Common mistakes

  • Using a[j] >= key — moves equal elements past key and breaks stability.
  • Swapping instead of shifting; correct but roughly 3× the writes.
  • Forgetting j >= 0 in the loop guard (or writing it after a[j] in a language that evaluates both).
  • Assuming binary insertion makes it O(n log n) — the shifts still dominate.

Interview patterns

  • Sort a nearly sorted array where each element is at most k away: insertion sort in O(nk), or a size-k heap in O(n log k).
  • Insertion sort on a linked list (LeetCode 147) — splice nodes into a sorted dummy list.
  • Explain why library sorts fall back to insertion sort for short ranges.
  • Merge a new element into a sorted array in place (the single-step version).
Interview questions on this
Mock interviews

Example problems

Sort Colors (Dutch National Flag)mediumMerge Intervalsmedium