Merge sort in Go
Sort an array by divide and conquer. Sort each half, then merge the two sorted halves into one sorted array.
- File
merge_sort.go, 44 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/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
// Package mergesort sorts a slice by merging.
package mergesort
import "cmp"
// Sort sorts a in place, in non-decreasing order. The sort is stable.
func Sort[T cmp.Ordered](a []T) {
buf := make([]T, (len(a)+1)/2)
sort(a, 0, len(a), buf)
}
func sort[T cmp.Ordered](a []T, lo, hi int, buf []T) {
if hi-lo <= 1 { // @line L1
return
}
mid := lo + (hi-lo)/2 // @line L2
sort(a, lo, mid, buf) // @line L3
sort(a, mid, hi, buf) // @line L4
merge(a, lo, mid, hi, buf) // @line L5
}
func merge[T cmp.Ordered](a []T, lo, mid, hi int, buf []T) {
b := buf[:mid-lo]
copy(b, a[lo:mid]) // @line L6
i, j, k := 0, mid, lo // @line L7
for i < len(b) && j < hi { // @line L8
if b[i] <= a[j] { // @line L9
a[k] = b[i]
i++
} else {
a[k] = a[j] // @line L10
j++
}
k++ // @line L11
}
for i < len(b) { // @line L12
a[k] = b[i] // @line L13
i++
k++
}
}
merge_sort_test.go 44 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
package mergesort
import (
"math/rand/v2"
"slices"
"testing"
)
func TestExample(t *testing.T) {
a := []int{38, 27, 43, 3, 9, 82, 10}
Sort(a)
if !slices.Equal(a, []int{3, 9, 10, 27, 38, 43, 82}) {
t.Errorf("got %v", a)
}
}
func TestEdges(t *testing.T) {
for _, a := range [][]int{{}, {1}, {2, 1}, {1, 1, 1}, {3, 2, 1}, {1, 2, 3}} {
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(61))
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