How Insertion Sort Works
Insertion sort keeps the front of the array sorted and slides each new value back into its place, the way you sort a hand of cards. Step through it and compare its cost with the alternatives.
- Waiting
- Being compared
- Just moved
- In final position
Step 1 of 95
Insertion sort, 12 values in random order.
Counters
- Comparisons
- 0
- Writes
- 0
- n
- 12
- Average case
- O(n²)
Settings
Two to 48 numbers. Sorted in exactly the order you type them.
Insertion sort
- 1
for 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 -= 1 - 7
a[j+1] = key
The same array, every algorithm
Comparisons on the values above, cheapest first. Writes in the second line. Run it on nearly sorted values to see the O(n log n) sorts lose.
- Merge3344 writes
- Quick3340 writes
- Insertion4042 writes
- Shell4637 writes
- Heap5166 writes
- Bubble6062 writes
- Selection6618 writes
How the seven compare
| Algorithm | Best | Average | Worst | Extra memory | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Shell | O(n log n) | O(n√n) | O(n²) | O(1) | No |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
Stable means equal values keep their original order.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(n) | O(n²) | O(n²) | O(1) |
Cost is proportional to the number of inversions, which is why nearly sorted input is close to linear.
How insertion sort works
Insertion sort treats the front of the array as a sorted hand and the rest as the deck. It takes the next value, shifts every larger value in the sorted part one place right, and drops the value into the gap. Because it only moves values that are genuinely in the way, its cost is proportional to how unsorted the input actually is.
- Treat the first element as a sorted region of one.
- Hold the next element aside as the key.
- Walk left through the sorted region, shifting every element larger than the key one position right.
- Drop the key into the gap that opens up. The sorted region is now one longer.
- Repeat to the end of the array.
Implementation
The same algorithm the visualiser is running, written to be read.
def insertion_sort(values):
for i in range(1, len(values)):
key = values[i]
j = i - 1
# Shift everything larger than the key one place right.
while j >= 0 and values[j] > key:
values[j + 1] = values[j]
j -= 1
values[j + 1] = key
return valuesWhen to use it
- Use it for small arrays. It has almost no overhead per element, which is why real library sorts — including Timsort and most quicksort implementations — switch to it below a few dozen elements.
- Use it on nearly sorted or streaming data: each new value usually needs one comparison and no shifts, so the total cost stays close to linear.
- Avoid it on large random arrays, where the shifting dominates and an O(n log n) sort wins by orders of magnitude.
Check yourself
If the animation made sense, these should too.
Why do real library sorts fall back to insertion sort for small arrays?
Because asymptotics ignore constants. Insertion sort has almost no per-element overhead: no recursion, no partitioning, no allocation, and sequential access the cache likes. Below a few dozen elements that beats an O(n log n) sort whose constant factor is much larger.
What makes its cost 'proportional to how unsorted the input is'?
Each element shifts past exactly the elements that are greater than it and to its left - that is, past its inversions. The total number of shifts is the number of inversions in the array, so nearly sorted input is nearly linear and reversed input is the full n²/2.