DSA Visualizer
SORT

Insertion Sort Visualizer

Watch each value slide left into a growing sorted part, the way you sort a hand of cards. Press play, or step through it.

Inserts each value into a growing sorted prefix. Great on small or nearly-sorted data (best case O(n)).

8
3
12
5
9
1
6
11
2
7
Insertion sort grows a sorted region on the left, sliding each new value back to where it belongs.
0
ComparesComparisons
0
SwapsSwaps
0
WritesWrites
1 / 75

Pseudocode

Insertion Sort
1for i in 1 .. n-1:
2 key = a[i]
3 j = i - 1
4 while j >= 0 and a[j] > key:
5 a[j+1] = a[j]
6 j = j - 1
7 a[j+1] = key

Legend

ComparingKeyShiftingSorted
Data

Tip: Space play/pause · ← → step

Learn insertion sort

Insertion Sort takes one value at a time and slides it left into a sorted part that grows from the front, shifting the bigger values over to make room.

Like bubble sort and selection sort, it is a comparison sort: it decides what goes where purely by comparing pairs of values.

All three are also in-place (they reuse the same array, O(1) extra memory) and simple to reason about. The trade-off is speed: each runs in O(n²) on average, so they shine on small or nearly-sorted inputs rather than huge datasets.

New to this O(…) notation? Start with the Big-O Playground →

Stable

Keeps equal values in their original relative order. Bubble & insertion are stable; selection is not.

In-place

Sorts within the array itself — no second array needed, so memory stays at O(1).

How insertion sort works

This is how most people sort a hand of playing cards. You pick up the next card, slide it left past every card that is bigger, and drop it into the gap. The cards on the left are always in order. That is the rule the whole algorithm protects.

The list is split into a sorted part on the left and an untouched part on the right. One value at a time crosses from right to left, and it is inserted exactly where it belongs, so the sorted part stays sorted as it grows.

It needs nothing special from the data. But unlike bubble and selection sort, it is strongly affected by the starting order, in a good way: the closer the list is to sorted, the less work there is to do.

A worked example: sorting 5, 2, 4, 1, 3

Type 5, 2, 4, 1, 3 into the custom array box above and step through it. Each row below is one value being placed:

Insertion sort on the list 5, 2, 4, 1, 3, value by value
WhenThe listWhat happened
Start5 2 4 1 3A single value, the 5, counts as a sorted part of length one.
Place the 22 5 4 1 31 comparison. The 5 is bigger, so it shifts right and the 2 drops in at the front.
Place the 42 4 5 1 32 comparisons. The 5 shifts right. The 2 is smaller than 4, so the scan stops there.
Place the 11 2 4 5 33 comparisons. The 5, 4 and 2 all shift right and the 1 lands at the front.
Place the 31 2 3 4 53 comparisons. The 5 and 4 shift right, the 2 stops the scan, and the 3 fills the gap.

That adds up to 9 comparisons, 11 writes and 0 swaps. While a value is sliding you will briefly see a duplicate in the bars, such as 5 5 4 1 3. That is the shift in progress: the key is safe in its variable and is about to overwrite one of the copies.

What i, j and key mean

i is the position of the value being placed. It starts at 1, because a single value on its own is already sorted.

key is a copy of that value, taken before anything moves.

j walks left through the sorted part, starting at i − 1. While a[j] is bigger than the key, that value is copied one slot to the right and j steps left. When the loop stops, the gap is at j + 1, and that is where the key goes. If the key is the smallest value so far, j runs off the front and reaches −1. That is expected, and it is why the loop checks j >= 0 first.

How many steps does insertion sort take?

It depends on the list, which is what makes this sort worth studying. On a sorted list of 5 values each key is compared once and stays put: 4 comparisons. On a reversed list every key slides all the way to the front: 1 + 2 + 3 + 4 = 10 comparisons. The shuffled example above landed in between, at 9.

In general the best case is n − 1 comparisons, which grows in step with the list and is written O(n). The worst case is n × (n − 1) ÷ 2, which grows with n × n and is written O(n²). A random list lands about halfway, which is still O(n²). Try the Nearly sorted and Reversed presets at the same size and compare the counters.

Best
O(n)
Average
O(n²)
Worst
O(n²)
Extra memory
O(1)
Stable
Yes

See the gap between those two growth rates for yourself in the Big-O Playground →

When insertion sort is the right choice

For short lists, for lists that are already nearly in order, and for data that arrives one item at a time, since each new item can be inserted into the sorted part without starting again. It is stable and needs no extra memory.

That combination is why real libraries use it as a building block: they split big inputs with a faster algorithm and hand the small pieces to insertion sort. Of the three simple sorts, this is the one you are most likely to meet in production code.

Mistakes beginners make

  • Not saving the key. The first shift overwrites a[i]. Without a copy, the value being placed is lost.
  • Checking the value before the bounds. Write j >= 0 and a[j] > key in that order. The other way round reads a[−1].
  • Putting the key at j instead of j + 1. When the loop stops, j points at the value that was not bigger. The gap is one to its right.
  • Using >= in the comparison. It shifts equal values for no reason and makes the sort unstable.

Insertion sort questions

Why is insertion sort fast on nearly sorted data?

Each value only slides left past the values that are bigger than it. If the list is almost in order, most values are already in place or one step away, so the inner loop stops almost immediately and the whole sort takes close to n steps.

Why does the Swaps counter stay at 0?

Insertion sort does not swap. It lifts one value out (the key), shifts the bigger values one slot to the right with single writes, and then writes the key into the gap. The Writes counter is the one to watch.

Is insertion sort used in real software?

Yes. Timsort, the sort built into Python and used by Java for objects, switches to insertion sort for short runs of data, because on small lists its simplicity beats cleverer algorithms.

Is insertion sort stable?

Yes. The scan stops as soon as it meets a value that is not bigger than the key, so the key is placed after any equal values and their original order is kept.

What is the key in insertion sort?

It is the value currently being placed. It is copied into a variable first because the shifting that follows overwrites the slot it came from.