Insertion Sort Explained
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 9 others run step by step in our free interactive visualizer.
▶ Launch Visualiser