# Insertion sort

yourbasic.org

Insertion sort can outperform more complicated algorithms for short lists and lists that are almost sorted.

Insertion sort is a simple sorting algorithm with **quadratic** worst-case running time,
but in some cases it’s still the algorithm of choice.

- It’s efficient for
**really small data sets**. It typically outperforms other simple quadratic algorithms, such as selection sort or bubble sort. - It’s
**adaptive**: it sorts data sets that are already substantially sorted efficiently. The time complexity is O(*nk*) when each element is at most*k*places away from its sorted position. - It’s
**stable**: it doesn’t change the order of elements with equal keys. - It’s
**in-place**: it only requires a constant amount of additional memory.

```
// InsertionSort sorts the elements of a in ascending order.
func InsertionSort(a []int) {
for j := 1; j < len(a); j++ {
// Invariant: a[:j] contains the same elements as
// the original slice a[:j], but in sorted order.
key := a[j]
i := j - 1
for i >= 0 && a[i] > key {
a[i+1] = a[i]
i--
}
a[i+1] = key
}
}
```

### Further reading

See Top 3 Quicksort optimizations for a fast Quicksort implementation that uses Insertion sort to improve performance.