Work one through by hand
Sort [5, 2, 9, 1].
[5, 2, 9, 1] → take 2, slide past 5 → [2, 5, 9, 1]
[2, 5, 9, 1] → take 9, already in place → [2, 5, 9, 1]
[2, 5, 9, 1] → take 1, slide past 9, 5, 2 → [1, 2, 5, 9]
Six comparisons and four shifts. Notice that 9 cost exactly one comparison because it was already larger than everything to its left — the algorithm does no work when an element is already in position, which is the property everything else about it follows from.
Why O(n²) worst and O(n) best
The outer loop runs n−1 times. The inner loop slides the current element back past however many larger elements sit to its left.
On reverse-sorted input every element must travel the full width of the sorted region, giving 1 + 2 + 3 + … + (n−1) = n(n−1)/2 comparisons — O(n²).
On already-sorted input every element fails its first comparison and stops immediately: n−1 comparisons and zero shifts, so O(n). Almost no other sort has a linear best case, and it is why insertion sort is the tail end of real library sorts.
Sorting the way you sort playing cards
Insertion sort builds a sorted region at the front of the array, one element at a time. Take the next element and slide it backwards past everything larger, until it sits in the right place.
That is exactly how most people sort a hand of cards, which is why it is the most intuitive of the quadratic sorts.
Sorting [5, 2, 4, 6, 1]:
| Step | Take | Array |
|---|
| Start | — | [5, 2, 4, 6, 1] |
| 1 | 2 | [2, 5, 4, 6, 1] |
| 2 | 4 | [2, 4, 5, 6, 1] |
| 3 | 6 | [2, 4, 5, 6, 1] |
| 4 | 1 | [1, 2, 4, 5, 6] |
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] # shift right - no swapping
j -= 1
arr[j + 1] = key # one write, at the end
return arr
The bold region is always sorted. That is the invariant, and it is what makes the algorithm easy to verify.
Note the shifting rather than swapping: each element moves once into its final gap, rather than being swapped repeatedly. That is why insertion sort does fewer writes than bubble sort for the same comparisons.
Why it beats the other quadratic sorts
| Algorithm | Comparisons | Writes | Best case | Stable |
|---|
| Insertion | O(n²) | O(n²) shifts | O(n) | Yes |
| Bubble | O(n²) | O(n²) swaps (3 writes each) | O(n) | Yes |
| Selection | O(n²) always | O(n) swaps | O(n²) | No |
Three properties matter, and together they explain why insertion sort is the one that survives in production code.
Adaptive. On nearly-sorted input the inner loop barely runs, so it approaches O(n). Bubble sort shares this; selection sort does not.
Stable. arr[j] > key shifts only strictly larger elements, so equal elements keep their order. Using >= would break it.
Online. It can sort a stream: each new element is inserted into the already-sorted portion without restarting. No other simple sort does this.
Plus the practical one: a very low constant factor. The inner loop is a comparison and a move, with no recursion, no allocation and sequential memory access.
Why real sorting libraries contain it
That low constant factor is why insertion sort is not merely a teaching example — it is inside the sort you actually use.
Timsort (Python, Java for objects) uses binary insertion sort for runs shorter than 32–64 elements, and its whole design is built around finding and extending naturally sorted runs, which is insertion sort's strength.
Introsort (C++ std::sort) recurses with quick sort down to a small threshold and finishes with a single insertion sort pass over the nearly-sorted whole.
The reason is that O(n log n) algorithms have overhead — recursion, partitioning, allocation — that dominates at small n. Below roughly 32 elements, insertion sort's simplicity wins outright.
So the accurate statement is not "insertion sort is slow". It is: insertion sort is the fastest known approach for small or nearly-sorted arrays, and that is precisely where library sorts delegate to it.
Why it is the sort that real libraries keep
Insertion sort is quadratic and still ships inside CPython's sort, Java's, and most C++ standard libraries. The reason is a property the complexity class does not capture, and it shows up immediately if you count comparisons on inputs of different shapes.
Things to try
- See the sorted region grow. Set Array Size to 12 and press Next Step repeatedly. The left-hand block is always sorted and always grows by exactly one per outer pass, no matter what the values are.
- Find the cheap elements. Watch for values that stop after a single comparison. Every one of those was already larger than its left neighbour — the algorithm spent no effort at all on them.
- Force the worst case. Press Randomize Array until you get something close to descending order, then Auto-Run. Every element crosses the entire sorted region and the shift count balloons toward n²/2.
- Scale the cost. Run a full sort at Array Size 5 and then at 20. Four times the elements takes roughly sixteen times the shifts, not four — quadratic growth is visible directly in the counter.
Where it is actually used
Insertion sort is not a toy. It has four properties that keep it in production code:
- Stable. Equal elements keep their original relative order, because sliding stops at the first element that is not strictly greater.
- In-place. O(1) extra memory — no auxiliary array, unlike merge sort.
- Adaptive. Cost is O(n + d) where d is the number of inversions. Nearly-sorted input is nearly linear.
- Online. It can sort a stream, inserting each element as it arrives without seeing the rest.
Together these are why virtually every industrial-strength sort — Timsort in Python and Java, introsort in C++ — recurses down with quicksort or merge sort and then hands subarrays below roughly 16 elements to insertion sort. At that size its tiny constant factor beats the recursive machinery outright.
Common mistakes
>= instead of > in the shift condition, which destroys stability.- Starting the outer loop at 0 rather than 1 — harmless, and it wastes a pass.
- Swapping instead of shifting, which triples the writes for no benefit.
- Using it on large random arrays. At n = 100,000 it is minutes rather than milliseconds.
- Expecting binary insertion sort to be O(n log n) overall. The comparisons are; the moves are not.
Key takeaway
Insertion sort grows a sorted prefix by sliding each new element back into place, which makes it O(n²) on random data and O(n) on sorted data. Stable, in-place, adaptive and online, it is the sort that real libraries fall back to once a divide-and-conquer sort has chopped the problem small enough — not despite being simple, but because being simple is what makes it fast at that scale.
Binary insertion sort
Finding the insertion point by scanning backwards is O(n) per element. Because the front region is sorted, binary search can find that point in O(log n) instead:
from bisect import bisect_right
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
pos = bisect_right(arr, key, 0, i) # O(log n) to find the gap
arr[pos+1:i+1] = arr[pos:i] # still O(n) to shift
arr[pos] = key
return arr
This reduces comparisons from O(n²) to O(n log n), and the moves remain O(n²) because the elements still have to be shifted.
That is worth it when comparisons are expensive — comparing long strings, or objects with a custom comparator — and not when they are cheap integer comparisons, where the extra bookkeeping costs more than it saves.
Note bisect_right rather than bisect_left: inserting after equal elements is what preserves stability.
Where it is used
- Inside Timsort and introsort for small runs, as above.
- Online sorting. Maintaining a sorted list as items arrive —
bisect.insort is exactly this. - Nearly-sorted data. A mostly-ordered log or time series with a few late arrivals.
- Very small arrays, where it is genuinely the fastest option.
- Embedded systems, where code size matters and the algorithm is a handful of instructions.
- Sorting linked lists, where the shifting becomes pointer rearrangement.
The bisect.insort case is the most common real-world appearance in Python: keeping a list sorted as items arrive is O(n) per insertion because of the shift, and it beats re-sorting the whole list every time.
Questions people ask
Is insertion sort ever better than quick sort? Yes — on arrays below roughly 32 elements, and on nearly-sorted data. That is why library sorts call it.
Is it stable? Yes, with a strict > comparison.
What is the best case? O(n), on already-sorted input — the inner loop never executes.
How does it compare with selection sort? Insertion sort is adaptive and stable; selection sort is neither, and does fewer writes.
Can it sort a stream? Yes — it is the only simple sort that is naturally online.
What is bisect.insort? Binary insertion into a sorted list: O(log n) to find the position, O(n) to shift. The standard way to maintain a sorted list in Python.
Recap in one screen
- Build a sorted region at the front, sliding each new element back into place.
- Shifting rather than swapping means fewer writes than bubble sort for the same comparisons.
- Adaptive (O(n) on sorted input), stable, online, and with a very low constant factor.
- That combination is why Timsort and introsort delegate to it for small and nearly-sorted runs.
- Binary insertion reduces comparisons to O(n log n); the moves stay O(n²).