Insertion Sort
Take the next value. Slide it left past anything larger. The sorted prefix grows by one.
Sort 7 values. The first value is a sorted prefix of one; each next value slides left into place.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 13, with their answers.
1 is next to 5 on its left. What happens?
Answer: Slide left. 5 > 1, so 1 slides one slot left.
4 is next to 5 on its left. What happens?
Answer: Slide left. 5 > 4, so 4 slides one slot left.
4 is next to 1 on its left. What happens?
Answer: Stop here. 1 <= 4, so 4 has found its place.
2 is next to 5 on its left. What happens?
Answer: Slide left. 5 > 2, so 2 slides one slot left.
2 is next to 4 on its left. What happens?
Answer: Slide left. 4 > 2, so 2 slides one slot left.
2 is next to 1 on its left. What happens?
Answer: Stop here. 1 <= 2, so 2 has found its place.
8 is next to 5 on its left. What happens?
Answer: Stop here. 5 <= 8, so 8 has found its place.
3 is next to 8 on its left. What happens?
Answer: Slide left. 8 > 3, so 3 slides one slot left.
3 is next to 5 on its left. What happens?
Answer: Slide left. 5 > 3, so 3 slides one slot left.
3 is next to 4 on its left. What happens?
Answer: Slide left. 4 > 3, so 3 slides one slot left.
3 is next to 2 on its left. What happens?
Answer: Stop here. 2 <= 3, so 3 has found its place.
7 is next to 8 on its left. What happens?
Answer: Slide left. 8 > 7, so 7 slides one slot left.
7 is next to 5 on its left. What happens?
Answer: Stop here. 5 <= 7, so 7 has found its place.
How it runs, step by step
Sort 7 values. The first value is a sorted prefix of one; each next value slides left into place.
Insertion sort on 5, 1, 4, 2, 8, 3, 7. Values are taken left to right and inserted into the sorted prefix.
Pick 1 at index 1 and find where it belongs in the sorted prefix.
Picking 1 at index 1. The sorted prefix covers indices 0 to 0.
5 is larger than 1, so 1 slides left.
Comparing 5 at index 0 with 1. 5 is larger, so 1 moves to index 0.
1 is the smallest so far and sits at index 0. Prefix sorted through index 1.
1 inserted at index 0. Indices 0 to 1 are now sorted.
Pick 4 at index 2 and find where it belongs in the sorted prefix.
Picking 4 at index 2. The sorted prefix covers indices 0 to 1.
5 is larger than 4, so 4 slides left.
Comparing 5 at index 1 with 4. 5 is larger, so 4 moves to index 1.
1 is not larger than 4, so 4 stays at index 1.
Comparing 1 at index 0 with 4. 4 stops at index 1.
4 is in place at index 1. Prefix sorted through index 2.
4 inserted at index 1. Indices 0 to 2 are now sorted.
Pick 2 at index 3 and find where it belongs in the sorted prefix.
Picking 2 at index 3. The sorted prefix covers indices 0 to 2.
5 is larger than 2, so 2 slides left.
Comparing 5 at index 2 with 2. 5 is larger, so 2 moves to index 2.
4 is larger than 2, so 2 slides left.
Comparing 4 at index 1 with 2. 4 is larger, so 2 moves to index 1.
1 is not larger than 2, so 2 stays at index 1.
Comparing 1 at index 0 with 2. 2 stops at index 1.
2 is in place at index 1. Prefix sorted through index 3.
2 inserted at index 1. Indices 0 to 3 are now sorted.
Pick 8 at index 4 and find where it belongs in the sorted prefix.
Picking 8 at index 4. The sorted prefix covers indices 0 to 3.
5 is not larger than 8, so 8 stays at index 4.
Comparing 5 at index 3 with 8. 8 stops at index 4.
8 is in place at index 4. Prefix sorted through index 4.
8 inserted at index 4. Indices 0 to 4 are now sorted.
Pick 3 at index 5 and find where it belongs in the sorted prefix.
Picking 3 at index 5. The sorted prefix covers indices 0 to 4.
8 is larger than 3, so 3 slides left.
Comparing 8 at index 4 with 3. 8 is larger, so 3 moves to index 4.
5 is larger than 3, so 3 slides left.
Comparing 5 at index 3 with 3. 5 is larger, so 3 moves to index 3.
4 is larger than 3, so 3 slides left.
Comparing 4 at index 2 with 3. 4 is larger, so 3 moves to index 2.
2 is not larger than 3, so 3 stays at index 2.
Comparing 2 at index 1 with 3. 3 stops at index 2.
3 is in place at index 2. Prefix sorted through index 5.
3 inserted at index 2. Indices 0 to 5 are now sorted.
Pick 7 at index 6 and find where it belongs in the sorted prefix.
Picking 7 at index 6. The sorted prefix covers indices 0 to 5.
8 is larger than 7, so 7 slides left.
Comparing 8 at index 5 with 7. 8 is larger, so 7 moves to index 5.
5 is not larger than 7, so 7 stays at index 5.
Comparing 5 at index 4 with 7. 7 stops at index 5.
7 is in place at index 5. Prefix sorted through index 6.
7 inserted at index 5. Indices 0 to 6 are now sorted.
Sorted. 13 comparisons and 8 swaps.
Result: the array is sorted in ascending order after 13 comparisons and 8 swaps.
Write it yourself
Define insertionSort(values) and return the same values in ascending order. It runs in your browser against this lesson's own 5 examples.
// Take the next value and slide it back through the sorted prefix until it fits.function insertionSort(values) { return values;}
Remember
- Nearly sorted input costs almost nothing, close to O(n).
- Stable, in place, and able to sort values as they arrive rather than all at once.
- The go-to sort for very small arrays, even inside fast sorts.
Topics covered
Related
Where this is used
Language runtimesTimsort's run builder
CPython's list.sort and Java's Arrays.sort for objects both run Timsort, which scans for stretches that are already in order and merges them. A stretch shorter than the minimum run length is extended by binary insertion sort, and since that minimum is capped at 64 in CPython, any list of fewer than 64 items is sorted by insertion sort alone. Timsort needs a sort that is stable and cheap on almost-ordered data, and that is the one job insertion sort is best at.
Standard librariesThe small-partition cutoff in quicksort
LLVM's libc++ std::sort stops recursing once a partition holds fewer than 24 elements and finishes it with insertion sort; the OpenJDK's dual-pivot quicksort does the same below 44. At that size the pivot selection, partition bookkeeping and call overhead cost more than the extra comparisons, and the whole partition sits in cache and is walked in order. The asymptotically worse algorithm wins because n never gets large enough for the asymptotics to matter.
GamesSweep and prune collision detection
Broad-phase collision detection keeps the bounding boxes of every object sorted by their extent along an axis, as Bullet Physics does in btAxisSweep3. When an object moves, each of its endpoints is pushed back into place by swapping with its neighbour until the order holds, which is exactly one insertion-sort step. Objects move only a little between frames, so last frame's ordering is nearly right and a handful of swaps repairs it. A sort that started from scratch each frame would do far more work to arrive at the same list.
Compressionbzip2's block sorter
bzip2 sorts every rotation of a block to build the Burrows-Wheeler transform, and once a bucket of rotations gets small its block sorter switches to a shell sort, which is insertion sort run repeatedly over shrinking gaps. The wide gaps move badly placed rotations a long way for very few moves, and by the time the gap reaches one the data is almost ordered, so the final plain insertion sort pass is nearly free.
Why it works this way
The inner loop condition is doing two careful things
&& short-circuits, so the bounds test has to come first. Written the other way round, any value that slides all the way into slot 0 makes the next check read a[-1]: an exception in Kotlin, undefined behaviour in C, where the read quietly succeeds off the front of the array and the swap that may follow writes there too. The comparison is also strict, so a[j - 1] > a[j] stops the moment it meets an equal value and leaves equal values in the order they arrived. Changing it to >= would keep swapping them past each other and destroy stability.
Why real implementations shift instead of swapping
A swap is three moves, and the value being placed gets moved again on every step of the inner loop. Saving that value in a temporary, sliding the larger elements one slot right, and writing it down once at the end does exactly the same comparisons with about a third of the moves. The swap version is easier to follow one step at a time, which is why it is shown here, but library code shifts: CPython's binarysort saves the value, runs a plain loop to slide the block right, then writes the value once.
The real cost is the number of inversions, not n squared
An inversion is any pair of values sitting in the wrong order relative to each other. Each swap in the inner loop removes exactly one of them, so the total work is n plus the inversion count. A reversed array has n(n - 1)/2 inversions, which is where the quadratic worst case comes from. An array where no element is more than k slots from home has at most kn, so the running time degrades smoothly with how unsorted the input is rather than jumping straight to the worst case.
Binary search finds the slot faster but does not make the sort faster
The prefix is already sorted, so you can binary search it for the insertion point and cut comparisons from O(n^2) to O(n log n). The elements still have to be shifted to open the gap, so the number of moves is unchanged and the total running time stays quadratic. It only pays off when one comparison costs far more than one move, such as sorting strings or objects through a user-supplied comparator, which is exactly the case CPython is in.
Read more
- Insertion sortWikipedia
- Comparison sorting visualisedUSF
- listsort.txt: how Timsort really worksCPython · github.com
- TimsortWikipedia
- Inversion (discrete mathematics)Wikipedia
Next up
- Bucket SortScatter values into equal value ranges, sort each small bucket, gather in order: linear on even data.
- Shell SortInsertion sort with gaps n/2, n/4, ..., 1, so far-apart values move in big strides first.
- TimSortFind natural ascending runs, extend short ones by insertion sort, then merge neighbouring runs.