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

  1. Sort a slice of structs by a string field case-insensitively with strings.ToLower in the comparison. What does the comparison allocate per call?
  2. Sort the same data once with sort.Slice and once with slices.SortFunc. Which one mistakes does the compiler catch?
  3. 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.

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

  9. 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.

  10. 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

Banner image