Insertion sort
Insertion sort grows a sorted prefix one value at a time: it takes the next value, shifts every larger value already in the sorted prefix one place to the right, then drops the new value into the gap left behind.
When it is the right choice
Insertion sort is a strong choice for small arrays and for data that is already nearly sorted, where its running time approaches O(n). It is also the base case many real merge sort implementations switch to below a small threshold, since its low overhead beats merge sort's recursion for tiny ranges. It is a poor choice for large, randomly ordered arrays, where it degrades to O(n²).
How it works
- For each position from the second item to the last, remember its value as the one being inserted.
- Compare the remembered value with the value immediately to its left in the sorted prefix.
- While the value to the left is greater, shift it one position to the right, opening a gap.
- Once a value to the left is no longer greater, or the start of the array is reached, place the remembered value into the gap left behind.
Worth noticing
- It performs no swaps at all, only shifts — a counter that only tracks swaps reports zero writes here, which is correct but easy to misread as 'nothing happened'.
- Its best case, O(n), is reached only on already-sorted input; on reversed input every insertion shifts the whole sorted prefix, giving O(n²).
- It is stable: a value is only ever shifted past strictly greater values, so equal values keep their original relative order.
Cost
- Best
- O(n)
- Average
- O(n²)
- Worst
- O(n²)
- Extra space
- O(1)
- Stable
- Yes