Insertion Sort

By Victor Arce

Insertion sort builds the sorted list one value at a time — exactly how most people sort a hand of playing cards. It takes the next value and slides it left past everything larger, until it drops into its correct place among the values already sorted.

Step through it below — each new value sinks left through the sorted part.

How it works

The front of the array is kept sorted. For each new value we compare it with its left neighbour and swap them while the neighbour is larger, sinking the value into position. Once it meets a value that is not larger, it has arrived, and the sorted region has grown by one.

This makes insertion sort adaptiveAdaptive: runs faster when the input is already partly sorted.: on already-sorted or nearly-sorted input each value barely moves, so it runs in close to O(n).

Cost

Insertion sort is O(n) in the best case (nearly-sorted input) and O(n²) on average and in the worst case. It is in-placeIn-place: sorts within the original array using only a little extra memory (no second array). (O(1) extra memory) and stableStable: equal values keep their original relative order after sorting. — equal values keep their order. Its adaptivity and low overhead make it the sort of choice for small or nearly-sorted arrays, and it is the building block inside hybrids like Timsort.

Back to Sorting Algorithms