Insertion Sort: Sliding Each Item Into Place

Insertion sort orders an array by taking each item in turn and shifting the larger items of the sorted part one place right until the gap left behind is where the item belongs. It is the elementary sort that adapts: the closer the input is to sorted, the less work it does. This card traces it and explains where that adaptiveness comes from.

The sorted part starts as the first item alone. For each index i from 1 onwards, the sort lifts the item there, called the key, and compares it with the sorted items to its left, nearest first. Each one larger than the key moves one place right. At the first item that is not larger, or at the front of the array, the key drops into the gap. A shift writes one item, where a swap writes two, which is one reason insertion sort beats bubble sort with the same number of moves. The trace sorts 6 2 9 4 1 7 3, with i on the index the key was lifted from and key on where it landed.

Every shift moves a larger item past a smaller one, which fixes exactly one inversion, a pair of items in the wrong order. The seven numbers hold 12 inversions, so the sort made 12 shifts. The comparisons are the shifts plus one stopping comparison for each key that did not reach the front: 2 and 1 went all the way, the other four stopped, and 12 + 4 is 16.

So insertion sort's cost is about n plus the number of inversions, and that number is what makes it adaptive. Sorted input has none: one comparison per key, no shifts, O(n) in all. Reversed input has n(n − 1)/2, every pair, and shuffled input about half that. Input in which every item sits a few places from where it belongs has few inversions per item, and costs close to O(n). The sort is stable because it stops at the first item that is not larger than the key, so the key never passes an item equal to it.

Finding the gap with a binary search instead, as Python's bisect.insort does for one item, cuts the comparisons to O(log n) per key, but the larger items still have to shift, so the sort stays O(n²). The costs, for an array of n items, are these.

The cues are a small array, input that is already nearly sorted, and data that arrives one item at a time, where each new item is inserted into a list kept sorted. Insertion sort's cost depends on how unsorted the input is, not only on its size, and that is why it outlives the other two: fast general-purpose sorts hand it their short or nearly sorted pieces.