Insertion sort in Go
Sort an array one item at a time. Take the next item and move it left until the item before it is not larger.
- File
insertion_sort.go, 20 lines- Level
- Native tests
- pass in this build
- Toolchain
- Go 1.27
- Test framework
- testing
- Run the tests
go test
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.
// Package insertionsort sorts a slice by insertion.
package insertionsort
import "cmp"
// Sort sorts a in place, in non-decreasing order. The sort is stable.
func Sort[T cmp.Ordered](a []T) {
for i := 1; i < len(a); i++ { // @line L1
key := a[i] // @line L2
j := i - 1 // @line L3
for j >= 0 && a[j] > key { // @line L4
a[j+1] = a[j] // @line L5
j-- // @line L6
}
a[j+1] = key // @line L7
}
}
insertion_sort_test.go 44 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.
package insertionsort
import (
"math/rand/v2"
"slices"
"testing"
)
func TestExample(t *testing.T) {
a := []int{5, 2, 4, 6, 1, 3}
Sort(a)
if !slices.Equal(a, []int{1, 2, 3, 4, 5, 6}) {
t.Errorf("got %v", a)
}
}
func TestEdges(t *testing.T) {
for _, a := range [][]int{{}, {1}, {2, 1}, {1, 1, 1}, {3, 2, 1}} {
b := slices.Clone(a)
Sort(b)
if !slices.IsSorted(b) {
t.Errorf("Sort(%v) = %v", a, b)
}
}
}
func TestRandom(t *testing.T) {
r := rand.New(rand.NewPCG(2150, 0))
for range 500 {
a := make([]int, r.IntN(41))
for i := range a {
a[i] = r.IntN(101) - 50
}
b, want := slices.Clone(a), slices.Clone(a)
Sort(b)
slices.Sort(want)
if !slices.Equal(b, want) {
t.Fatalf("Sort(%v) = %v", a, b)
}
}
}
What the next level needs
- I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work