Insertion Sort Explained
Insertion Sort builds a sorted list one item at a time and excels on nearly-sorted data. Learn how it works, its O(n) best case, and where it is used.
On this page +
Insertion Sort works the way most people sort a hand of playing cards: take the next card and insert it into its correct position among the cards already in your hand. It is simple, stable, adaptive, and surprisingly fast on small or nearly-sorted arrays — which is why hybrid sorts like Tim Sort and Introsort use it internally.
How Insertion Sort works #
Start with the second element. Compare it backwards against the sorted region to its left, shifting larger elements one position right until you find the gap where it belongs, then drop it in. Repeat for every element. The sorted region grows from left to right.
Pseudocode #
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]
j = j - 1
a[j+1] = keyWhy it is adaptive #
On nearly-sorted data each element only shifts a short distance, so Insertion Sort approaches O(n) — its best case. On reversed data it hits the O(n²) worst case. This adaptivity makes it ideal for small subarrays, which is why Tim Sort and Introsort hand off small partitions to Insertion Sort. It is stable and uses O(1) space.
When to use it #
Use Insertion Sort for small arrays (roughly under 16 elements), nearly-sorted data, or streaming data that arrives one element at a time. See it fly on a nearly-sorted array in the visualizer.
Frequently asked questions
What is the best case for Insertion Sort? +
Why do fast sorts switch to Insertion Sort? +
See it in motion
Watch this algorithm and nine others run step by step, with live pseudocode and comparison counters.
Launch the visualiser Software engineer at a stealth-stage startup, and previously a front-end engineer for around a year and a half.