The Story That Makes Insertion Sort Obvious
At every moment, the cards already in your hand are sorted. You never touch the cards still on the table until it is their turn. You grow a sorted pile one card at a time, always inserting the new card into its rightful place.
That is Insertion Sort — exactly, with no embellishment. If you can sort a hand of cards, you already understand the algorithm.
Formally, Insertion Sort splits the array into a sorted part (on the left) and an unsorted part (on the right). It repeatedly takes the first unsorted element — the key — and shifts larger sorted elements one step right to open a gap, then drops the key into that gap. The sorted region grows by one each pass until nothing unsorted remains.
Insertion Sort never searches for "the smallest element." It simply assumes everything to the left is already sorted and finds the right home for one new element at a time. This is why it is online (it can sort data as it streams in) and adaptive (it gets dramatically faster when the data is already close to sorted).
The Algorithm in Four Plain-English Steps
The amber card (key = 1) is lifted out while the pointer sweeps left; every card larger than 1 will be slid right to make room before the key drops into place.
Hands-On: Watch Every Line of Code Execute
This is the heart of the tutorial. Press Play (or step through manually) and watch two things move together: the highlighted line of Python on the right, and the animated array on the left. The status bar tells you exactly what the active line is doing to the data at that instant. Use Shuffle to try a fresh random array.
When arr[j + 1] = arr[j] lights up, watch a red card slide right into the
dashed gap. When arr[j + 1] = key lights up, the amber key finally drops
home and the sorted-green region grows by one. The while line lights up on
every comparison — that is where Insertion Sort spends its time.
The Full Python Implementation
Here is the same algorithm as a clean, copy-ready function, plus a tiny driver that prints the array before and after sorting.
def insertion_sort(arr):
# Treat index 0 as a sorted sub-list of size 1, then grow it.
for i in range(1, len(arr)):
key = arr[i] # the card we lift "into our hand"
j = i - 1 # last index of the sorted part
# Shift every sorted element bigger than key one slot right.
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # slide the bigger element right
j -= 1 # keep walking left
arr[j + 1] = key # drop key into the opened gap
return arr
# --- driver ---
data = [6, 3, 8, 2, 7, 1, 5]
print("Before:", data)
insertion_sort(data)
print("After: ", data)A Verbose Version That Narrates Each Pass
Run this once to see the sorted region grow — it prints the array after every insertion, mirroring the animation above.
def insertion_sort_verbose(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
print(f"Pass {i}: inserted {key:>2} -> {arr}")
return arr
insertion_sort_verbose([6, 3, 8, 2, 7, 1, 5])Why Use Insertion Sort? The Real Benefits
while rarely runs. Runtime
collapses toward linear time. It costs roughly O(n + d) where d
is the number of out-of-order pairs (inversions).
Unlike Merge Sort or Quick Sort, Insertion Sort does not need the whole list up front. Each new element can be inserted into the already-sorted portion the moment it arrives. This makes it ideal for streaming inputs and live, incrementally maintained lists.
When to Use It — and When Not To
sort() instead.Time & Space Complexity
| Case | When It Happens | Comparisons / Shifts | Time |
|---|---|---|---|
| Best | Array already sorted | Inner loop runs once per pass, no shifts | O(n) |
| Average | Randomly ordered data | ~n²/4 comparisons and shifts | O(n²) |
| Worst | Array sorted in reverse | ~n²/2 comparisons and shifts | O(n²) |
| Space | Any input (in-place) | One key variable, no extra array | O(1) auxiliary |
The outer for runs n−1 times. The inner while can run up to
i times. Multiply them and you get the quadratic O(n²) behaviour. The only
thing that saves you is data that is already in order — then the while
exits immediately and you get the O(n) best case.
Best Case vs Worst Case, Side by Side
| Pass (key) | Comparisons | Shifts |
|---|---|---|
| 2 | 1 | 0 |
| 3 | 1 | 0 |
| 4 | 1 | 0 |
| 5 | 1 | 0 |
| Total | 4 ≈ n | 0 |
| Pass (key) | Comparisons | Shifts |
|---|---|---|
| 4 | 1 | 1 |
| 3 | 2 | 2 |
| 2 | 3 | 3 |
| 1 | 4 | 4 |
| Total | 10 ≈ n²/2 | 10 |
How One Pass Flows
key = arr[i] — lift the first unsorted element out, leaving a conceptual gap at index i.j = i - 1 — aim a pointer at the last element of the sorted region, ready to compare.while arr[j] > key — copy each larger element one slot right and walk the pointer left. The gap travels with you.arr[j + 1] = key — once you find a smaller element (or hit the start), the key falls into the gap. Sorted region grew by one.Insertion Sort vs Its Cousins
| Property | Insertion Sort | Bubble Sort | Selection Sort | Merge Sort |
|---|---|---|---|---|
| Best case | O(n) | O(n) | O(n²) | O(n log n) |
| Average / worst | O(n²) | O(n²) | O(n²) | O(n log n) |
| Extra space | O(1) | O(1) | O(1) | O(n) |
| Stable? | Yes | Yes | No | Yes |
| Adaptive? | Yes — strongly | Somewhat | No | No |
| Online? | Yes | No | No | No |
| Best for… | Small / nearly-sorted | Teaching only | Few writes needed | Large general data |
Among the simple O(n²) sorts, Insertion Sort is almost always the one to pick: it is stable, adaptive, online, and has the smallest constant factor in practice. It beats Bubble Sort and Selection Sort on real-world, partly-ordered data — which is exactly why production sorting libraries embed it for their smallest sub-arrays.
Golden Rules
arr[j] > key (strictly greater), not >=. The strict
comparison is what keeps the sort stable — equal elements never jump
over each other.
sort() functions behave on small runs.