Insertion sort

Insertion sort is how most people sort a hand of cards: pick up the next card and slide it into the right place among the cards already in order. It is slow on long random lists, but very fast on short or nearly sorted ones, which is why real sorting libraries still use it.

Bars being sorted, a sorted part on the left and one bar sliding back into it past the larger bars
Bars being sorted, a sorted part on the left and one bar sliding back into it past the larger bars

The idea

Keep the front of the list sorted. At the start that sorted part is just the first value. Take the next value and compare it with the value before it. If that one is larger, swap them and compare again, one place further back. Stop when the value before is not larger, or when the value reaches the front. The sorted part has grown by one. Repeat with every value up to the end.

An example

Take 5, 1, 4, 2, 8. Pass 1 takes 1: 5 is larger, so they swap, and 1 reaches the front: 1, 5, 4, 2, 8. Pass 2 takes 4: it swaps with 5, then stops at 1: 1, 4, 5, 2, 8. Pass 3 takes 2: it swaps with 5 and with 4, then stops at 1: 1, 2, 4, 5, 8. Pass 4 takes 8, which is already larger than 5, so one comparison is enough. That is 7 comparisons and 4 swaps. Bubble sort needs 9 comparisons on the same list, selection sort 10.

Swaps equal inversions

An inversion is a pair of values in the wrong order. Swapping two neighbours that are out of order removes exactly one inversion, and insertion sort only ever swaps such neighbours. So it makes exactly as many swaps as the start list has inversions, the same number as bubble sort. Each pass also makes at most one comparison that does not lead to a swap, the one that stops it. So the comparisons are the inversions plus at most n − 1.

Adaptive: fast when the list is nearly sorted

Because the work is the number of inversions plus about n, insertion sort is fast whenever there are few inversions. A sorted list takes n − 1 comparisons and no swaps. A list where every value is only a few places from home takes time close to n. Only a list far from sorted, such as a reversed one with n(n − 1)/2 inversions, takes time proportional to n². On a random list the average is about n²/4 swaps.

Where it is used

Insertion sort is stable, needs no extra memory, and has very little overhead. For short lists it beats algorithms that are faster on paper. Many library sorts, such as Timsort in Python and Java and the introsort used in C++, switch to insertion sort for small pieces of the list, typically up to a few dozen values. It also suits data that arrives one value at a time, because each new value can be inserted as soon as it comes.

Explore it

Open the app and press Play, or press Step to go one comparison at a time. The value being inserted has its own colour, the value it is compared with is highlighted, and the sorted part is green. Unlike bubble sort and selection sort, the green part is not final: a later, smaller value can still slide into it. Try a nearly sorted list to see how short the passes are, then a reversed one.

Frequently asked questions

What is the time complexity of insertion sort?

O(n²) in the worst and average case, and O(n) in the best case, a list that is already sorted. More precisely, it takes time proportional to n plus the number of inversions. It needs only O(1) extra memory.

What is the difference between insertion sort and selection sort?

Selection sort scans the whole unsorted part to find the smallest value, so it always makes n(n − 1)/2 comparisons but few swaps. Insertion sort takes the next value as it comes and moves it back only as far as needed, so it makes fewer comparisons, especially on nearly sorted lists, but more swaps.

What is binary insertion sort?

A version that finds where the new value belongs with a binary search in the sorted part, which takes about log n comparisons instead of up to n. The values still have to be shifted to make room, so the number of moves, and the O(n²) worst case, stay the same.

Is insertion sort stable?

Yes. A value moves back only past values that are strictly larger, so equal values keep their original order.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Try insertion sort