Have you ever sorted a hand of playing cards? You pick up cards one at a time and slide each one into the correct position among the ones you already hold. That is exactly how insertion sort works. It builds a sorted section at the start of the list, and each new item is inserted into its correct position within that section.
The Key Idea
The list is divided into two parts:
- Sorted region — starts with just the first item; grows by one each round.
- Unsorted region — shrinks by one each round.
At each step, take the first item from the unsorted region and shift it left through the sorted region until it finds its correct position.
Step-by-Step Example
Starting with [5, 3, 8, 1, 4]:
| Round | Item to insert | Sorted region after insertion |
|---|---|---|
| 1 | 3 | [3, 5] |
| 2 | 8 | [3, 5, 8] |
| 3 | 1 | [1, 3, 5, 8] |
| 4 | 4 | [1, 3, 4, 5, 8] |
In round 3, the value 1 is smaller than 8, 5, and 3, so it shifts all three to the right and ends up at position 0.
Unlike selection sort, insertion sort does not search the whole unsorted region each time. It only looks at the sorted region. On nearly-sorted lists this means it may need to shift very few items, making it much faster in practice.
Python Implementation
def insertion_sort(items):
for i in range(1, len(items)):
key = items[i] # the item to insert
j = i - 1
# Shift larger items one position to the right
while j >= 0 and items[j] > key:
items[j + 1] = items[j]
j -= 1
items[j + 1] = key # insert in the correct position
return items
numbers = [5, 3, 8, 1, 4]
print(insertion_sort(numbers)) # [1, 3, 4, 5, 8]
Notice the inner while loop shifts items to the right rather than swapping, which is more efficient than bubble sort's approach.
Walk through the algorithm with a small list (4–5 items) on paper before trying to understand the code. Seeing the physical movement of items makes the logic much clearer.
Performance
| Scenario | Comparisons | Why |
|---|---|---|
| Already sorted | O(n) | Each new item is already in place — no shifts needed |
| Reverse sorted | O(n²) | Every new item must shift past all sorted items |
| Random order | O(n²) average | Shifts needed on average for each item |
This is what makes insertion sort special: it is the only simple O(n²) algorithm that can run in O(n) time on already-sorted input.
For large lists of random data, insertion sort is as slow as bubble sort and selection sort. Python's built-in sorted() uses Timsort, which actually includes insertion sort as one part — applied to small segments where it performs best.
When to Use Insertion Sort
Insertion sort is genuinely useful when:
- The list is small (fewer than about 20 items).
- The list is nearly sorted and only a few items are out of place.
- Items arrive one at a time and the list must remain sorted at all times.
Practice Problems
Trace insertion sort on [4, 2, 7, 3]. Show the state of the list at the end of each round.
Show answer
Why does insertion sort perform better than bubble sort on a nearly-sorted list?