29 lines
487 B
Go
29 lines
487 B
Go
package sort
|
|
|
|
// BinaryInsertionSort is an implementation of binary insertion sort algorithm.
|
|
// Wikipedia: https://en.wikipedia.org/wiki/Insertion_sort#Variants
|
|
func BinaryInsertionSort(a []int) []int {
|
|
for i := 1; i < len(a); i++ {
|
|
v := a[i]
|
|
first := 0
|
|
last := i
|
|
|
|
for first < last {
|
|
mid := first + (last-first)/2
|
|
if v < a[mid] {
|
|
last = mid
|
|
} else {
|
|
first = mid + 1
|
|
}
|
|
}
|
|
|
|
for j := i; j > first; j-- {
|
|
a[j] = a[j-1]
|
|
}
|
|
|
|
a[first] = v
|
|
}
|
|
|
|
return a
|
|
}
|