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
Insertion sort, 12 values in random order.
Counters
- Comparisons
- 0
- Writes
- 0
- n
- 12
- Average case
- O(n²)
Settings
More options
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 |
Scroll the table sideways for the rest of the columns.
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
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, Timsort and most quicksort implementations among them, 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.