Insertion sort

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.

// 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]
        a[i+1] = key

Further reading

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

Share this page: