insertion sort Algorithm
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.
However, insertion sort provides several advantages:
Simple implementation: Jon Bentley shows a three-line c version, and a five-line optimized version
Efficient for (quite) small data sets, much like other quadratic sorting algorithmsAdaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each component in the input is no more than K places away from its sorted position
Stable; i.e., makes not change the relative order of components with equal keys
//Package sorts a package for demonstrating sorting algorithms in Go
package sorts
func insertionSort(arr []int) []int {
for out := 1; out < len(arr); out++ {
temp := arr[out]
in := out
for ; in > 0 && arr[in-1] >= temp; in-- {
arr[in] = arr[in-1]
}
arr[in] = temp
}
return arr
}