Insertion sort builds a sorted prefix one value at a time. It picks the next unsorted value, walks it leftward past any larger values (shifting them right as it goes), and drops it into the gap. After every pass the prefix is one value longer, and when the prefix spans the whole array the sort is done.
Press play, or step through it one comparison at a time. Orange highlights the comparison, yellow is a shift in progress, and green marks the sorted prefix.
Ready. 14 values, unsorted.
0 comparisons · 0 shifts
Ready. 14 values, unsorted.
- Comparing
- Shifting
- Sorted prefix
Code
- def insertion_sort(a):
- n = len(a)
- for i in range(1, n):
- key = a[i]
- j = i - 1
- while j >= 0 and a[j] > key:
- a[j + 1] = a[j]
- j -= 1
- a[j + 1] = key
- return a
Try Worst case to watch every value shift all the way to the front, then Best case to see each value stay put after a single comparison. That gap between
the two is the difference between O(n²) and O(n).
Time and space complexity
| Case | Complexity | Why |
|---|---|---|
| Best | O(n) | Already sorted. Each value needs one comparison and zero shifts. |
| Average | O(n²) | Random order. Roughly n²/4 shifts. |
| Worst | O(n²) | Reverse sorted. Every value shifts all the way to the front. |
| Space | O(1) | Sorts in place. Only a temporary for the key. |
| Stable | Yes | Equal values never shift past each other. |
That O(n) best case is what makes insertion sort adaptive. The fewer inversions
in the input, the fewer shifts it does, and nearly-sorted data finishes in nearly
linear time. That property is why Timsort (Python, Java) uses insertion sort for
short runs.
Step by step
- Start with index 1. Index 0 is a sorted prefix of one value.
- Save the value at the current index as the key.
- Compare the key against values in the sorted prefix, moving right to left.
- Each value larger than the key shifts one position right.
- When you find a value that is not larger (or reach the start), drop the key into the gap.
- Move to the next index and repeat until the whole array is sorted.
Worked example
Sorting [5, 2, 4, 1]:
| Pass | Key | Shifts | Result | What happened |
|---|---|---|---|---|
| 1 | 2 | 1 | [2, 5, 4, 1] | 5 shifts right, 2 drops into index 0. |
| 2 | 4 | 1 | [2, 4, 5, 1] | 5 shifts right, 4 drops in after 2. |
| 3 | 1 | 3 | [1, 2, 4, 5] | 5, 4 and 2 all shift right, 1 drops into index 0. |
Three passes, five shifts total. Compare that with bubble sort on the same input, which needs three passes and six swaps.
When to use it
| Reach for it when | Avoid it when |
|---|---|
| The input is small (under ~20 values) | The input is large and in random order |
| The data is nearly sorted or arrives one item at a time | You need guaranteed O(n log n) on all inputs |
| You need a stable in-place sort with minimal overhead | Writes are expensive and you want fewer moves overall (use selection sort) |
| You are building a hybrid sort that needs a fast small-array fallback | The values have a bounded range and a linear-time sort like counting sort is cheaper |
The code
Every version below is the shift-based variant shown in the animation. The key is saved, larger values slide right, and the key is placed into the gap.
def insertion_sort(a):
n = len(a)
for i in range(1, n):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return a
nums = [5, 1, 4, 2, 8]
insertion_sort(nums)
print(nums)
Common questions
What is the time complexity of insertion sort?
O(n²) on average and in the worst case: each of the n values may need to be compared against every value already sorted before it. The best case is O(n), because an already-sorted array needs only one comparison per value and no shifts at all.
Is insertion sort stable?
Yes. It only shifts values that are strictly greater than the key, so two equal values never change their relative order.
Why is it called insertion sort?
Because of what the animation shows. Each unsorted value is picked up and inserted into its correct position within the already-sorted prefix, like sliding a card into the right spot in a hand you are holding.
How is insertion sort different from bubble sort?
Both are O(n²) and stable, but they move data differently. Bubble sort repeatedly swaps neighbours across the whole array. Insertion sort grows a sorted prefix one value at a time, shifting larger values right to make room. That means fewer writes and much better performance on nearly-sorted input.
Should I use insertion sort in real code?
For large arrays, no — use your language’s built-in sort, which is O(n log n). But insertion sort is the best choice for very small arrays (under ~20 elements), which is why hybrid algorithms like Timsort and introsort switch to it for short runs. It is also ideal when data arrives one item at a time and the collection must stay sorted after each addition.
What is the advantage over selection sort?
Insertion sort is adaptive: nearly-sorted input costs close to O(n). Selection sort always does the same number of comparisons regardless of input order. Insertion sort is also stable; selection sort is not (in its standard form).