Insertion Sort

What is insertion sort?

Insertion sort builds a sorted list one value at a time. It is how most people sort a hand of cards: pick up the next card, then slide it left until it sits in the right spot.

The left part of the list is always sorted. Each round takes the first value from the unsorted part and moves it left, past every bigger value, until the value to its left is smaller or equal. Then the sorted part is one value longer.

It is simple, it sorts in place, and it is very fast on lists that are already almost sorted. That last part is why real sorting libraries still use it.

How it works, step by step

Press play above. Blue bars are being compared, orange bars are being swapped. Watch one value travel left, one swap at a time, until it stops.

1. Treat the first value as a sorted list of one.
2. Take the next value, at index i. Set j = i.
3. While j > 0 and the value on the left, a[j - 1], is bigger than a[j], swap them and move j one step left.
4. When the left neighbor is smaller or equal (or you reach the front), stop. The value is in place.
5. Move on to the next i and repeat until the end of the list.

In the code, the while line holds both checks: stay inside the list, and keep going only while the left value is bigger. Each time it is true, the swap line below it runs. Every compare in the demo lights up that while line.

Time and space complexity

The work depends on how far each value has to travel. That distance is the number of bigger values sitting to its left.

Best case, O(n): the list is already sorted. Each new value is compared once with its left neighbor, finds it smaller, and stays. That is n − 1 comparisons and no swaps. Try the “nearly sorted” preset and see how short the run is.

Worst case, O(n²): the list is reversed. Every new value is the smallest so far, so it walks all the way to the front. That is 1 + 2 + … + (n − 1), about n²/2 swaps.

Average case, O(n²): on a shuffled list each value walks about halfway back, which is still about n²/4 swaps.

Space is O(1). It only swaps values inside the list and keeps two indexes.

Common mistakes

• Starting at i = 0. The first value has nothing to its left, so the outer loop starts at 1.
• Checking a[j - 1] before checking j > 0. At the front of the list a[j - 1] would read the wrong value (or crash). Put j > 0 first so the check stops in time.
• Using >= instead of >. Equal values would pass each other, and the sort would stop being stable.
• Forgetting to move j left after a swap, which loops forever.

A common speed-up is to shift the bigger values right instead of swapping, then drop the value into the gap at the end. It does the same comparisons with fewer writes. The version here swaps, so every move is visible.

When to use it

Insertion sort is a real tool, not just a classroom exercise. Use it when:

• The list is small, say under 20 to 50 values. Its low overhead beats fancier sorts there.
• The list is nearly sorted, like a sorted list with a few new values added at the end.
• Values arrive one at a time and you want the list sorted after each one.

This is why hybrid sorts use it. Timsort (Python’s built-in sort) and introsort (used in many C++ libraries) switch to insertion sort for small pieces. For large shuffled lists, use your language’s built-in sort: O(n log n) wins by a mile.

Questions

Is insertion sort stable?

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

Is insertion sort better than bubble sort?

Usually, yes. Both are O(n²), but insertion sort stops each value as soon as it is in place, so it does less work, especially on nearly sorted lists.

What is the difference between insertion sort and selection sort?

Insertion sort takes the next value and finds its place among the sorted ones. Selection sort finds the smallest remaining value and puts it next. Insertion sort adapts to sorted input; selection sort always does the same number of comparisons.