A simple sorting algorithm that builds the final sorted array one item at a time, much like how you might sort playing cards in your hands.
Overview
How the sorted region grows
Treat the first element as a sorted region of length one. Take the next element, and slide it left past every element larger than it until it sits in the right place. The sorted region is now length two. Repeat until the sorted region is the whole array.
This is how nearly everyone sorts a hand of playing cards, and the correspondence is exact: you hold a sorted fan, pick up a new card, and push it in at the right spot rather than re-sorting the whole hand.
Parameters
12
Visualization
Step: 0
Click Randomize or Step to begin sorting.
Algorithm Insight
Insertion Sort maintains a sorted sub-list and inserts new elements into their correct position.
1.Assume the first element is already sorted.
2.Pick the next element as the Key.
3.Shift sorted elements that are greater than the Key to the right.
4.Insert the Key into its correct slot.
Complexity
Average CaseO(N²)
Space ComplexityO(1)
Insertion Sort: A Practical Guide
Build the sorted portion one element at a time, sliding each new value back to where it belongs. Quadratic in general, but genuinely the fastest choice on small or nearly-sorted arrays.
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.
example_01.pyPython
def insertion(a):
a = a[:]
comps = shifts = 0
for i in range(1, len(a)):
key, j = a[i], i - 1
while j >= 0:
comps += 1
if a[j] > key:
a[j + 1] = a[j]
shifts += 1
j -= 1
else:
break
a[j + 1] = key
return a, comps, shifts
def selection(a):
a = a[:]
comps = swaps = 0
for i in range(len(a)):
m = i
for j in range(i + 1, len(a)):
comps += 1
if a[j] < a[m]:
m = j
if m != i:
a[i], a[m] = a[m], a[i]
swaps += 1
return a, comps, swaps
import random
random.seed(7)
n = 20
shapes = {
"sorted": list(range(n)),
"nearly sorted": list(range(n)),
"random": random.sample(range(n), n),
"reversed": list(range(n))[::-1],
}
shapes["nearly sorted"][5], shapes["nearly sorted"][6] = \
shapes["nearly sorted"][6], shapes["nearly sorted"][5]
print("n = %d" % n)
print("%-15s %11s %11s" % ("input shape", "insertion", "selection"))
for name, data in shapes.items():
_, ic, _ = insertion(data)
_, sc, _ = selection(data)
print("%-15s %11d %11d" % (name, ic, sc))
# That first column is the point. Insertion sort costs 19 comparisons on
# sorted input and 190 on reversed -- a factor of ten between the best and
# worst case on the same size. It is ADAPTIVE: its cost tracks how far the
# input already is from sorted.
#
# Selection sort's column does not move. 190 comparisons regardless,
# because it scans the whole remaining region to find each minimum whether
# or not the data is already in order.
print()
print("worst case n(n-1)/2 =", n * (n - 1) // 2)
# So: real data is often nearly sorted, and small arrays are always
# nearly sorted relative to n^2 being small anyway. Both are why the
# hybrid sorts hand short runs to insertion sort instead of recursing.
print()
print("comparisons on a 10-element nearly-sorted list:")
small = list(range(10))
small[3], small[4] = small[4], small[3]
_, c1, _ = insertion(small)
_, c2, _ = selection(small)
print(" insertion %d, selection %d" % (c1, c2))
Output
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²).
Run it in Python
The sorted region grows from the left and each new item is shifted back into place. The printout marks the boundary with |, and the last section shows why real sort implementations switch to this one for small inputs.
insertion_sort.pyPython 3
# Insertion sort: keep a sorted prefix, and insert each next item into it.
def insertion_sort(a, show=True):
a = a[:]
shifts = 0
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key: # slide bigger items one place right
a[j + 1] = a[j]
shifts += 1
j -= 1
a[j + 1] = key # the hole left behind is where key goes
if show:
front = " ".join(f"{x:>2}" for x in a[:i + 1])
back = " ".join(f"{x:>2}" for x in a[i + 1:])
print(f"insert {key:>2}: {front} | {back}")
return a, shifts
data = [12, 11, 13, 5, 6]
print("start :", data)
out, shifts = insertion_sort(data)
print("sorted:", out, f"({shifts} shifts)")
print()
for name, sample in [("sorted", [1, 2, 3, 4, 5, 6, 7, 8]),
("nearly sorted", [1, 2, 4, 3, 5, 6, 8, 7]),
("reversed", [8, 7, 6, 5, 4, 3, 2, 1])]:
_, s = insertion_sort(sample, show=False)
print(f"{name:>14}: {s} shifts")
print()
print("Cost tracks disorder, not size. CPython's own sort exploits exactly this.")
Output
How the code works
key = a[i]The item is copied out first, which frees its slot. Everything after this is shifting items into the hole and finally dropping key into wherever the hole ended up.
while j >= 0 and a[j] > key:Two exits: running off the front, or meeting something that is not bigger. The second is the early exit that makes an already sorted input cost O(n) — the condition fails at once, every time.
a[j + 1] = a[j]A shift, not a swap. One write per displaced item rather than three, which is why insertion sort beats bubble sort in practice even though they share a complexity class.
a[j + 1] = keyThe + 1 undoes the last j -= 1 of the loop. Getting this index wrong is the single most common bug in this algorithm.
shiftsThe shift count is the number of inversions in the input. That is why “nearly sorted” is not a vague description here — it is a measurable quantity, and it is exactly what this sort charges you for.
Change one thing
Run it on a list of 20 random numbers, then on the same list sorted. The shift count collapses; no O(n²) sort should be able to do that.
Replace the shifting loop with repeated swaps. Same output, three times the writes — and now you have written bubble sort inside out.
Binary-search for the insertion point instead of scanning. Comparisons drop to O(n log n); the shifts, and therefore the running time, do not move at all.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
Insertion sort's running time is driven by:
Each shift fixes one inversion, so a nearly sorted list is nearly free. "Nearly sorted" is a measurable quantity here, not a vague description.
Why does the inner loop shift items rather than swap them?
The item being placed is held in key, so the hole can simply be moved. That constant-factor saving is why insertion sort beats bubble sort in practice.
Real sort implementations switch to insertion sort for small partitions because:
At n around 16 the O(n²) with a tiny constant beats the O(n log n) with a heavier one. CPython's own sort does exactly this.
Cheat sheet
Insertion Sort
Treat the first element as a sorted region of length one. Take the next element, and slide it left past every element larger than it until it sits in the right place. The sorted region is now length two. Repeat until the sorted region is the whole array.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.