# Insertion sort vs. selection sort (time complexity and performance)

yourbasic.org

## Insertion sort

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

- It’s efficient for
**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. - It has good branch prediction characteristics, typically limited to a single misprediction per key.

```
// 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
}
}
```

## Selection sort

In practice, selection sort generally performs worse than insertion sort.

- It doesn’t adapt to data and always performs a quadratic number of comparisons.
- However, it
**moves each element at most once**.

```
// SelectionSort sorts the elements of a in ascending order.
func SelectionSort(a []int) {
for j := 0; j < len(a)-1; j++ {
// Invariant: a[:j] contains the first j elements
// of the final sorted slice.
minPos := j
for i := j + 1; i < len(a); i++ {
if a[i] < a[minPos] {
minPos = i
}
}
a[j], a[minPos] = a[minPos], a[j]
}
}
```

## Further reading

See Optimized quicksort algorithm explained for a fast Quicksort implementation that uses Insertion sort to improve performance.