sort, slices.SortFunc and maps.Keys
Sorting is one of the places where Go changed its mind: sort.Slice with a reflection-based less function was the standard answer for years, and the generic slices package replaced it with type-safe functions that take a comparison. The comparison returns a negative number, zero or a positive one, which cmp.Compare produces for any ordered type. The generics lesson showed the package; this one sorts with it.
slices.Sort for ordered types
slices.Sort sorts a slice of any ordered type in place, ascending, with a pattern-defeating quicksort that is fast on real data and falls back to insertion sort on small runs. For a descending order, slices.SortFunc takes the comparison and can reverse it; the result is still a sort, not a filtered copy, so the input slice is the output.
package main
import (
"fmt"
"slices"
)
func main() {
nums := []int{3, 1, 2}
slices.Sort(nums)
fmt.Println(nums)
words := []string{"pear", "apple", "fig"}
slices.Sort(words)
fmt.Println(words)
desc := []int{3, 1, 2}
slices.SortFunc(desc, func(a, b int) int {
return b - a
})
fmt.Println(desc)
}
go run basic.go
[1 2 3]
[apple fig pear]
[3 2 1]
The ints and the strings came out in their natural order and the last slice in reverse, because the comparison returned b - a. That subtraction is fine for small numbers and wrong for values whose difference overflows an int, which is why cmp.Compare exists and is what the next block uses.
Two keys with cmp.Or
cmp.Or returns the first non-zero comparison, so it chains keys the way a SQL ORDER BY does. The comparison in this block sorts by age and then by name, and the reader can see the order of the keys in the order they are written. A tie on the first key falls through to the second, and a tie on all keys leaves the two elements as the sort found them.
package main
import (
"cmp"
"fmt"
"slices"
"strings"
)
type person struct {
Name string
Age int
}
func main() {
people := []person{
{"grace", 45},
{"ada", 36},
{"linus", 36},
{"alan", 41},
}
slices.SortFunc(people, func(a, b person) int {
return cmp.Or(
cmp.Compare(a.Age, b.Age),
strings.Compare(a.Name, b.Name),
)
})
fmt.Println(people)
}
go run struct.go
[{ada 36} {linus 36} {alan 41} {grace 45}]
The two thirty-six-year-olds came out as ada then linus, which is the second key at work. %v printed the structs without field names because the fields are unexported by convention here; a caller reading the table still sees the values in declaration order.
Stable when the order matters
A plain sort may reorder equal keys, and usually does. SortStableFunc keeps the input order of equal keys, which is what a two-pass sort needs: sort by the minor key, then by the major one, and the stability preserves the first pass inside the second. The cost is extra memory and a merge step, so use it only when equal keys have a meaningful original order.
package main
import (
"cmp"
"fmt"
"slices"
)
type event struct {
kind string
seq int
}
func main() {
events := []event{
{"b", 1}, {"a", 2}, {"b", 3}, {"a", 4},
}
stable := slices.Clone(events)
slices.SortStableFunc(stable, func(x, y event) int {
return cmp.Compare(x.kind, y.kind)
})
fmt.Println("stable:", stable)
unstable := slices.Clone(events)
slices.SortFunc(unstable, func(x, y event) int {
return cmp.Compare(x.kind, y.kind)
})
fmt.Println("plain:", unstable)
}
go run stable.go
stable: [{a 2} {a 4} {b 1} {b 3}]
plain: [{a 2} {a 4} {b 1} {b 3}]
The stable sort kept every a before every b in the order they appeared, and the plain one could have swapped them. On a four-element slice the unstable result is not guaranteed to differ, which is the trap: the bug appears on a bigger input in production, not in the test.
Finding after sorting
slices.BinarySearch returns the index of the value and whether it was found; when it is not found, the index is where it would be inserted, which is the same contract as sort.Search. It requires a sorted slice, and slices.IsSorted is the cheap check a program can make before trusting a slice it received from elsewhere.
package main
import (
"fmt"
"slices"
)
func main() {
nums := []int{10, 20, 30, 40, 50}
i, found := slices.BinarySearch(nums, 30)
fmt.Println("30 at", i, found)
i, found = slices.BinarySearch(nums, 35)
fmt.Println("35 at", i, found, "insert there")
sorted := []int{5, 1, 4, 2}
if slices.IsSorted(sorted) {
fmt.Println("sorted")
} else {
fmt.Println("not sorted, sorting")
slices.Sort(sorted)
}
fmt.Println(sorted)
}
go run search.go
30 at 2 true
35 at 3 false insert there
not sorted, sorting
[1 2 4 5]
Thirty was at index 2 of five, and thirty-five reported index 3 with false: inserting there keeps the slice sorted. The last block sorted a slice only after checking it, which is the defensive form of the same idea and costs one linear pass.
Exercises
- Sort a slice of structs by a string field case-insensitively with strings.ToLower in the comparison. What does the comparison allocate per call?
- Sort the same data once with sort.Slice and once with slices.SortFunc. Which one mistakes does the compiler catch?
- Keep a sorted slice of ids and insert a new id with slices.BinarySearch and slices.Insert. How many elements move per insert?
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does slices.Sort require of a slice?
Answer
An ordered element type, and it sorts the slice in place
The generic version handles the comparison itself for ordered types.
-
What does this program print?
package main import ( "fmt" "slices" ) func main() { nums := []int{3, 1, 2} slices.Sort(nums) fmt.Println(nums) words := []string{"pear", "apple", "fig"} slices.Sort(words) fmt.Println(words) desc := []int{3, 1, 2} slices.SortFunc(desc, func(a, b int) int { return b - a }) fmt.Println(desc) }Answer
[1 2 3] / [apple fig pear] / [3 2 1]
The first two sorts are ascending and the third reverses the comparison.
-
What does a comparison function return?
Answer
A negative number, zero or a positive number
cmp.Compare produces that three-way result, and the sort uses its sign.
-
What does this program print?
package main import ( "cmp" "fmt" "slices" "strings" ) type person struct { Name string Age int } func main() { people := []person{ {"grace", 45}, {"ada", 36}, {"linus", 36}, {"alan", 41}, } slices.SortFunc(people, func(a, b person) int { return cmp.Or( cmp.Compare(a.Age, b.Age), strings.Compare(a.Name, b.Name), ) }) fmt.Println(people) }Answer
[{ada 36} {linus 36} {alan 41} {grace 45}]
The age is the first key and the name breaks the tie between the two 36s.
-
What does cmp.Or do in a multi-key comparison?
Answer
Returns the first comparison that is not zero
It falls through the keys in the order written, like a SQL ORDER BY.
-
What does the first line of this program print?
package main import ( "cmp" "fmt" "slices" ) type event struct { kind string seq int } func main() { events := []event{ {"b", 1}, {"a", 2}, {"b", 3}, {"a", 4}, } stable := slices.Clone(events) slices.SortStableFunc(stable, func(x, y event) int { return cmp.Compare(x.kind, y.kind) }) fmt.Println("stable:", stable) unstable := slices.Clone(events) slices.SortFunc(unstable, func(x, y event) int { return cmp.Compare(x.kind, y.kind) }) fmt.Println("plain:", unstable) }Answer
stable: [{a 2} {a 4} {b 1} {b 3}] / plain: [{a 2} {a 4} {b 1} {b 3}]
The stable sort keeps the original order inside each group of equal kinds.
-
When is SortStableFunc worth its cost?
Answer
When equal keys must keep their original order
Stability is a promise about ties, and it costs memory and a merge.
-
What does the second line of this program print?
package main import ( "fmt" "slices" ) func main() { nums := []int{10, 20, 30, 40, 50} i, found := slices.BinarySearch(nums, 30) fmt.Println("30 at", i, found) i, found = slices.BinarySearch(nums, 35) fmt.Println("35 at", i, found, "insert there") sorted := []int{5, 1, 4, 2} if slices.IsSorted(sorted) { fmt.Println("sorted") } else { fmt.Println("not sorted, sorting") slices.Sort(sorted) } fmt.Println(sorted) }Answer
30 at 2 true / 35 at 3 false insert there / not sorted, sorting / [1 2 4 5]
BinarySearch reports the insertion point and false when the value is absent.
-
Where is the value that BinarySearch cannot find inserted?
Answer
At the returned index, which keeps the slice sorted
The index is the insertion point, which is what makes the result useful.
-
Why is sort.Slice no longer the first choice?
Answer
It uses reflection and a less function, while slices.Sort is type-safe
The generic functions catch type mistakes at compile time and avoid reflection.
The code on this page was run with go 1.26.10 on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev