Insertion Sort
Task: Sort this array in ascending order
Why we need Insertion Sort
Analogy
- Imagine you are holding a hand of playing cards, and you pick up one more.
- You do not re-sort the whole hand. You slide the new card left past the cards bigger than it, and drop it in.
- The cards you already had stay in order the entire time.
- That is insertion sort, and you have done it a hundred times without naming it.
What is insertion sort?
Definition
Insertion sort builds a sorted part on the left, one value at a time.
It takes the next unsorted value and inserts it into its correct position among the values already sorted, shifting the larger ones right to make room.
A single value is already sorted, so the work starts at the second one.
One insertion, step by step
Suppose the sorted part is 3 5 8 and the next value is 4.
Lift 4 out of the array. That leaves a hole where it used to be. Now walk left: 8 is bigger, so it slides right into the hole, and the hole moves with it. 5 is bigger too, so it slides right as well. 3 is smaller, so the walk stops, and the hole that is left is exactly where 4 belongs.
Nothing was swapped. Values were shifted, and the lifted value was dropped in once.
The sorted part grows from the left
Do that for every value and the sorted region grows by one each round, until it is the whole array.
Note
This is the mirror of bubble sort. There, the finished region grows from the right, because each pass carries the largest value to the end. Here it grows from the left, because each round adds one more value to a sorted prefix.
Try it
Try it yourself
Lift a value out, shift the bigger ones right, drop it in
Press step to watch one comparison, round to place a whole value, and sort to run to the end. Watch the lifted value travel left while the bars underneath it shift right.
Why it is fast on nearly sorted data
The cost of a round is how far back the value has to travel. A value that is already bigger than everything before it travels nowhere: one comparison, no shifts.
So on an array that is already sorted, every round is a single comparison and insertion sort finishes in O(n).
Watch out
That is not a special case bolted on. It falls straight out of the inner loop, which stops the moment it meets something smaller. Bubble sort needs an explicit check to get the same best case; insertion sort gets it for free.
In code
def insertion_sort(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 return arr print(insertion_sort([5, 3, 8, 4, 2]))# [2, 3, 4, 5, 8]The while loop is the shifting. It stops as soon as it finds a value smaller than the key, and arr[j + 1] = key drops the key into the hole that is left.
What it costs
| Case | Time | Space | Why |
|---|---|---|---|
| Best | O(n) | O(1) | Already sorted, so no value ever has to move. |
| Average | O(n2) | O(1) | Each value travels about halfway back. |
| Worst | O(n2) | O(1) | Reverse order, so every value travels the whole way. |
Space is O(1): it sorts in place, and the only extra storage is the one value being carried.
Insertion sort against bubble sort
| Insertion sort | Bubble sort | |
|---|---|---|
| The move | Lift one value out and shift the bigger ones right | Compare neighbours and swap the pair |
| Sorted part grows from | The left | The right |
| Best case | O(n) | O(n) |
| Worst case | O(n2) | O(n2) |
| On nearly sorted data | Very fast, most rounds do nothing | Fast only if you add the early exit |
The complexities match, but the constants do not. Insertion sort moves each value once per shift, where bubble sort swaps repeatedly, so in practice it wins on small and nearly sorted inputs. It is what real libraries fall back to when a partition gets small enough.
Where you have seen it
- Sorting a hand of playing cards
- Putting a book back on a shelf, sliding it in among the ones already in order
- Inside merge sort and quick sort, which switch to it once a chunk is small
Quick recap
- Take the next value and hold it
- Shift everything bigger one place right
- Drop it into the hole that is left
The sorted part grows from the left, one value each round, and a value already in place costs almost nothing.
Key takeaway
Sort it the way you sort cards in your hand: take the next one and slide it back to where it belongs.