Pseudocode
func Insertion(s []int) {
for i := 1; i < len(s); i++ {
for j := i; j > 0 && s[j-1] > s[j]; j-- {
s[j-1], s[j] = s[j], s[j-1]
}
}
}Properties
| Worst Time | Average Time | Best Time | Worst Space | Average Space | Stability | Adaptive |
|---|---|---|---|---|---|---|
| Stable | Adaptive |
Insertion sort is adaptive: efficient for data sets that are already substantially sorted, the time complexity is when each element in the input is no more than places away from its sorted position
Relation to Number of Inversions
The number of exchanges used by insertion sort is equal to the number of inversions
The number of compares is at least equal to the number of inversions and at most equal to the number of inversions plus the array size minus 1
Proof: Every exchange involves two inverted adjacent entries and thus reduces the number of inversions by one, and the array is sorted when the number of inversions reaches zero. Every exchange corresponds to a compare, and an additional compare might happen for each value of i from 1 to N-1 (when a[i] does not reach the left end of the array).