Hands-On High Performance with Go

Insertion sort

Insertion sort is a sorting algorithm that constructs an array one item at a time until it results in a sorted array. It's not very efficient, but it does have a simple implementation and is quick for very small datasets. The array is sorted in place, which can also help reduce the memory footprint of the function call.

This standard library algorithm for insertionSort can be found in the following code snippet. We can use the following code snippet to deduce that insertion sort is an average case of an O(n²) algorithm. This is due to the fact that we iterate through a 2D array and manipulate data:

func insertionSort(data Interface, a, b int) {  for i := a + 1; i < b; i++ {    for j := i; j > a && data.Less(j, j-1); j-- { data.Swap(j, ...