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.

// 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.

// 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 this page: