Insertion Sort
Learn how insertion sort builds the sorted array one element at a time, like sorting a hand of cards.
Insertion Sort
Insertion sort builds the sorted array one element at a time. It takes each element and inserts it into its correct position within the already-sorted left portion, shifting larger elements right to make room. Think of how you sort a hand of playing cards — you pick up one card at a time and slot it into the right place.
How it works
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # the element to be inserted
j = i - 1
# shift elements larger than key one position to the right
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
# insert key into its correct position
arr[j + 1] = key
return arrTrace through an example
Start: [5, 3, 8, 1, 2]
i=1, key=3:
arr[0]=5 > 3 → shift right: [5, 5, 8, 1, 2]
insert 3 at index 0: [3, 5, 8, 1, 2]
i=2, key=8:
arr[1]=5 < 8 → stop
insert 8 at index 2: [3, 5, 8, 1, 2] (no change)
i=3, key=1:
arr[2]=8 > 1 → shift: [3, 5, 8, 8, 2]
arr[1]=5 > 1 → shift: [3, 5, 5, 8, 2]
arr[0]=3 > 1 → shift: [3, 3, 5, 8, 2]
insert 1 at index 0: [1, 3, 5, 8, 2]
i=4, key=2:
arr[3]=8 > 2 → shift: [1, 3, 5, 8, 8]
arr[2]=5 > 2 → shift: [1, 3, 5, 5, 8]
arr[1]=3 > 2 → shift: [1, 3, 3, 5, 8]
arr[0]=1 < 2 → stop
insert 2 at index 1: [1, 2, 3, 5, 8]When insertion sort wins
Despite its O(n²) worst case, insertion sort has properties that make it genuinely useful:
O(n) on nearly-sorted arrays — if each element is only a few positions from its correct spot, insertion sort is very fast.
Online algorithm — it can sort elements as they arrive, one at a time, without seeing the whole array upfront.
Efficient for small arrays — the constant factors are so low that Python's Timsort uses insertion sort for small subarrays (size ≤ 64).
Stable — equal elements preserve their original relative order.
Python's built-in Timsort is a hybrid — it breaks the array into small chunks, sorts each with insertion sort, then merges them with merge sort. Insertion sort's simplicity and cache friendliness make it ideal for small inputs, while merge sort handles the large-scale merging efficiently.
Complexity
| Case | Time | Space |
|---|---|---|
| Best (nearly sorted) | O(n) | O(1) |
| Average | O(n²) | O(1) |
| Worst (reverse sorted) | O(n²) | O(1) |