Insertion Sort Algorithm
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
However, insertion sort provides several advantages:
1. 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
2. Stable; i.e., makes not change the relative order of components with equal keys
package InsertionSort
func InsertionSort(array []int) {
for itemIndex, itemValue := range array {
for itemIndex != 0 && array[itemIndex-1] > itemValue {
array[itemIndex] = array[itemIndex-1]
itemIndex -= 1
}
array[itemIndex] = itemValue
}
}
