Go Sorting in Depth
Sorting places the values of a slice into a chosen order. Go sorts in place, so the slice itself holds the new order afterward.
Sorting by hand with sort.Interface
ByLength is a string slice type with the three methods. Less compares the lengths of two words, so the shortest word lands first.
package main
import (
"fmt"
"sort"
)
type ByLength []string
func (b ByLength) Len() int {
return len(b)
}
func (b ByLength) Less(i, j int) bool {
return len(b[i]) < len(b[j])
}
func (b ByLength) Swap(i, j int) {
b[i], b[j] = b[j], b[i]
}
func main() {
words := ByLength{"banana", "fig", "kiwi"}
sort.Sort(words)
fmt.Println(words)
}SortFunc sorts in falling order
cmp.Compare(a, b) would sort in rising order. Passing the inputs swapped turns the result around, so the biggest number lands first.
package main
import (
"cmp"
"fmt"
"slices"
)
func main() {
nums := []int{2, 8, 5}
slices.SortFunc(nums, func(a, b int) int {
return cmp.Compare(b, a)
})
fmt.Println(nums)
}BinarySearch on a rising slice
The slice is already in rising order, as the search needs. The search reports the index and true for a hit, and an index with false for a miss.
package main
import (
"fmt"
"slices"
)
func main() {
nums := []int{2, 5, 8}
i, found := slices.BinarySearch(nums, 5)
fmt.Println(i, found)
j, ok := slices.BinarySearch(nums, 6)
fmt.Println(j, ok)
}A stable sort keeps equal scores in order
Ana and Bo both hold a score of 90. The stable sort orders by score, and Ana stays ahead of Bo, as in the starting slice.
package main
import (
"cmp"
"fmt"
"slices"
)
type Result struct {
Name string
Score int
}
func main() {
results := []Result{{"Ana", 90}, {"Bo", 90}, {"Cy", 80}}
slices.SortStableFunc(results, func(a, b Result) int {
return cmp.Compare(b.Score, a.Score)
})
fmt.Println(results)
}Example
package main
import (
"cmp"
"fmt"
"slices"
)
type Entry struct {
Name string
Score int
}
func main() {
board := []Entry{{"Ana", 70}, {"Bo", 95}, {"Cy", 80}}
slices.SortFunc(board, func(a, b Entry) int {
return cmp.Compare(a.Score, b.Score)
})
fmt.Println(board)
scores := []int{}
for _, e := range board {
scores = append(scores, e.Score)
}
i, found := slices.BinarySearch(scores, 80)
fmt.Println(i, found)
fmt.Println(board[i].Name)
}Key points
- sort.Interface asks a type for three methods named Len, Less and Swap.
- Less reports whether the value at index i must come before the value at index j.
- sort.Sort reads the three methods and orders the values in place.
- slices.SortFunc orders a slice with a comparison function given as an argument.
- The comparison function returns a negative number, zero or a positive number.
- slices.BinarySearch finds a value only in a slice sorted in rising order.
- A stable sort keeps equal values in the order they started in.
In this example, SortFunc orders the board by score in rising order. A second slice collects the scores in that same order. BinarySearch looks for 80 in the sorted scores and finds it at index 1. The last line prints the name at that index on the board, and the name is Cy.
Note
sort.Sort makes no promise about equal values, so a stable sort is the safe pick when their order matters.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Go Playground
Exercise
What must be true of a slice before slices.BinarySearch can search it?