Insertion Sort
Slide each item into place.
Insertion sort works like adding cards to a hand you're already holding in order. Take the next card, and slide it left, past every bigger card, until it fits. It's O of N squared in general, but it's very fast when the list is almost sorted already.

- Like cards in your hand
- Slide each one left
- Fast on nearly sorted lists
Sliding into place
We take each item, from the second one onward, and call it key. While the item to its left is bigger, we shift that item one place right. When we find a smaller item, or reach the start, the key drops into the gap. Run it. The sorted part on the left grows by one item each pass.
def insertion_sort(nums):
for i in range(1, len(nums)):
key = nums[i]
j = i - 1
while j >= 0 and nums[j] > key:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = key
print(f"pass {i}: {nums}")
insertion_sort([5, 2, 9, 1, 7])pass 1: [2, 5, 9, 1, 7] pass 2: [2, 5, 9, 1, 7] pass 3: [1, 2, 5, 9, 7] pass 4: [1, 2, 5, 7, 9]
Why insertion sort matters
On a nearly sorted list, each item only slides a step or two, so insertion sort is close to O of N. That's why real world sorting algorithms, including Python's own, use insertion sort for small pieces. It's also stable, meaning equal items keep their original order.
| key | value |
|---|---|
| Time | O(n²), but O(n) if nearly sorted |
| Space | O(1) |
| Stable | equal items keep order |
| Used inside | Python's own sort |
Summary
Insertion sort slides each item left into place. It's great for small or nearly sorted lists. Next, a much faster idea. Merge sort.
Key takeaways- Take the next item
- Slide it left
- Great when nearly sorted