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

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.

Share: