## Algorithm

for i = 2:n,
for (k = i; k > 1 and a[k] < a[k-1]; k--)
swap a[k,k-1]
*→ invariant: a[1..i] is sorted*
end

## Properties

- Stable
- O(1) extra space
- O(n
^{2}) comparisons and swaps
- Adaptive: O(n) time when nearly sorted
- Very low overhead

## Discussion

Although it is one of the elementary sorting algorithms with
O(n^{2}) worst-case time, insertion sort is the
algorithm of choice either when the data is nearly sorted
(because it is adaptive) or when the problem size is small
(because it has low overhead).

For these reasons, and because
it is also stable, insertion sort is often used as the recursive base
case (when the problem size is small) for higher overhead
divide-and-conquer sorting algorithms, such as
merge sort or quick sort.

## Key

- Black values are sorted.
- Gray values are unsorted.
- A red triangle marks the algorithm position.