Benchmark Sorting in Go Across sort and slices Packages

Go has two sorting APIs, and which one you pick changes the cost by 1.5 to 10 times on the same data. The older sort package works through an interface or a less(i, j) closure. The newer slices package (Go 1.21) is generic and works on the slice directly. This article sorts 1,000 and 100,000 random integers and the same number of 32 byte structs with every combination, then looks at what the algorithm does with ordered input and what a stable sort costs, so the choice can be made with numbers. It is a benchmark of what is there in Go 1.25, not an argument about algorithms.

It uses the method in benchmarking a Go function properly. Struct size matters here, as in struct layout and padding, and allocation counts connect to reducing allocations. The cornerstone is the Go performance guide.

The contenders

• sort.Ints and slices.Sort: sort a slice of an ordered type with <.
• sort.Slice(s, less): sorts any slice with a closure, using reflection to swap elements.
• sort.Sort(data): sorts anything implementing Len, Less and Swap.
• slices.SortFunc(s, cmp): generic, with a three way comparison function that returns a negative, zero or positive int.
• sort.SliceStable and slices.SortStableFunc: the stable versions, which keep equal elements in their original order.

Both packages use the same underlying algorithm, pattern defeating quicksort, for the unstable sorts. The differences are in how an element is compared and moved. Each benchmark copies the source into a work buffer first and then sorts it, so the copy is in every row equally.

package main

import (
	"cmp"
	"flag"
	"fmt"
	"math/rand/v2"
	"slices"
	"sort"
	"testing"
)

func init() {
	testing.Init()
	flag.Set("test.benchtime", "150ms")
}

type rec struct {
	ID    int
	Score int
	Name  string
}

type byScore []rec

func (s byScore) Len() int           { return len(s) }
func (s byScore) Less(i, j int) bool { return s[i].Score < s[j].Score }
func (s byScore) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

func median(f func(b *testing.B)) (float64, int64) {
	const runs = 5
	xs := make([]float64, 0, runs)
	var r testing.BenchmarkResult
	for i := 0; i < runs; i++ {
		r = testing.Benchmark(f)
		xs = append(xs, float64(r.T.Nanoseconds())/float64(r.N))
	}
	slices.Sort(xs)
	return xs[runs/2], r.AllocsPerOp()
}

func ints(n int) []int {
	r := rand.New(rand.NewPCG(1, 2))
	s := make([]int, n)
	for i := range s {
		s[i] = r.IntN(1 << 30)
	}
	return s
}

func recs(n int) []rec {
	r := rand.New(rand.NewPCG(3, 4))
	s := make([]rec, n)
	for i := range s {
		s[i] = rec{ID: i, Score: r.IntN(1000), Name: "n"}
	}
	return s
}

func runInts(name string, n int, f func([]int)) {
	src := ints(n)
	buf := make([]int, n)
	ns, al := median(func(b *testing.B) {
		for b.Loop() {
			copy(buf, src)
			f(buf)
		}
	})
	fmt.Printf("  %-38s %12.0f ns %9.1f ns/elem %3d allocs\n", name, ns, ns/float64(n), al)
}

func runRecs(name string, n int, f func([]rec)) {
	src := recs(n)
	buf := make([]rec, n)
	ns, al := median(func(b *testing.B) {
		for b.Loop() {
			copy(buf, src)
			f(buf)
		}
	})
	fmt.Printf("  %-38s %12.0f ns %9.1f ns/elem %3d allocs\n", name, ns, ns/float64(n), al)
}

func main() {
	for _, n := range []int{1000, 100000} {
		fmt.Printf("sorting %d random ints (the copy of the input is included in every row)\n", n)
		runInts("sort.Ints", n, sort.Ints)
		runInts("sort.Slice with a less func", n, func(s []int) { sort.Slice(s, func(i, j int) bool { return s[i] < s[j] }) })
		runInts("slices.Sort", n, slices.Sort[[]int])
		runInts("slices.SortFunc with cmp.Compare", n, func(s []int) { slices.SortFunc(s, cmp.Compare[int]) })
		fmt.Println()
		fmt.Printf("sorting %d 32 byte structs by one field\n", n)
		runRecs("sort.Sort with Len/Less/Swap", n, func(s []rec) { sort.Sort(byScore(s)) })
		runRecs("sort.Slice", n, func(s []rec) { sort.Slice(s, func(i, j int) bool { return s[i].Score < s[j].Score }) })
		runRecs("slices.SortFunc", n, func(s []rec) { slices.SortFunc(s, func(a, b rec) int { return cmp.Compare(a.Score, b.Score) }) })
		runRecs("sort.SliceStable", n, func(s []rec) { sort.SliceStable(s, func(i, j int) bool { return s[i].Score < s[j].Score }) })
		runRecs("slices.SortStableFunc", n, func(s []rec) { slices.SortStableFunc(s, func(a, b rec) int { return cmp.Compare(a.Score, b.Score) }) })
		fmt.Println()
	}
	const n = 100000
	fmt.Printf("slices.Sort on %d ints in different orders\n", n)
	for _, kind := range []string{"random", "already sorted", "reversed", "all equal"} {
		src := ints(n)
		switch kind {
		case "already sorted":
			slices.Sort(src)
		case "reversed":
			slices.Sort(src)
			slices.Reverse(src)
		case "all equal":
			for i := range src {
				src[i] = 7
			}
		}
		buf := make([]int, n)
		ns, _ := median(func(b *testing.B) {
			for b.Loop() {
				copy(buf, src)
				slices.Sort(buf)
			}
		})
		fmt.Printf("  %-38s %12.0f ns %9.1f ns/elem\n", kind, ns, ns/float64(n))
	}
}

sorting 1000 random ints (the copy of the input is included in every row)
  sort.Ints                                     10650 ns      10.7 ns/elem   0 allocs
  sort.Slice with a less func                   40667 ns      40.7 ns/elem   2 allocs
  slices.Sort                                   11038 ns      11.0 ns/elem   0 allocs
  slices.SortFunc with cmp.Compare              43757 ns      43.8 ns/elem   0 allocs

sorting 1000 32 byte structs by one field
  sort.Sort with Len/Less/Swap                  47463 ns      47.5 ns/elem   1 allocs
  sort.Slice                                    71808 ns      71.8 ns/elem   3 allocs
  slices.SortFunc                               47538 ns      47.5 ns/elem   0 allocs
  sort.SliceStable                             253136 ns     253.1 ns/elem   3 allocs
  slices.SortStableFunc                        105110 ns     105.1 ns/elem   0 allocs

sorting 100000 random ints (the copy of the input is included in every row)
  sort.Ints                                   5649681 ns      56.5 ns/elem   0 allocs
  sort.Slice with a less func                 9365664 ns      93.7 ns/elem   2 allocs
  slices.Sort                                 5678461 ns      56.8 ns/elem   0 allocs
  slices.SortFunc with cmp.Compare            8465198 ns      84.7 ns/elem   0 allocs

sorting 100000 32 byte structs by one field
  sort.Sort with Len/Less/Swap                6919173 ns      69.2 ns/elem   1 allocs
  sort.Slice                                  8235643 ns      82.4 ns/elem   3 allocs
  slices.SortFunc                             6385619 ns      63.9 ns/elem   0 allocs
  sort.SliceStable                           62422236 ns     624.2 ns/elem   3 allocs
  slices.SortStableFunc                      22666589 ns     226.7 ns/elem   0 allocs

slices.Sort on 100000 ints in different orders
  random                                      5611411 ns      56.1 ns/elem
  already sorted                                74799 ns       0.7 ns/elem
  reversed                                      98438 ns       1.0 ns/elem
  all equal                                     73952 ns       0.7 ns/elem

Integers

sort.Ints and slices.Sort are the same code. Since Go 1.22 sort.Ints calls slices.Sort, and the table shows it: 10.7 and 11.0 ns per element at 1,000, 56.5 and 56.8 at 100,000. Use either. The generic form is typed, so there is nothing to forget.

Passing a comparison function costs a call per comparison. slices.SortFunc with cmp.Compare[int] took 4 times as long at 1,000 elements and 1.5 times at 100,000. The comparison went from an inlined < to an indirect call that the compiler cannot inline into the sorting loop. For a type that < works on, use slices.Sort and skip the function.

sort.Slice is the slowest and allocates. It took 9.37 ms against 5.65 ms at 100,000, and made two allocations, because it needs a reflection based swapper for an arbitrary slice type, plus the closure. It remains the one liner people know. For an int slice, it was 66 percent slower than slices.Sort.

Structs

A 32 byte record (two ints and a string) sorted by one integer field:

slices.SortFunc was fastest at 100,000 and tied with sort.Sort at 1,000. The comparison here is a call in all three, so the call cost that hurt on ints is similar across the group, and the difference is the swap: the generic version moves the 32 byte element directly, sort.Sort goes through a method on the interface, and sort.Slice goes through reflection. sort.Slice was 29 percent slower than slices.SortFunc at 100,000 and 51 percent slower at 1,000.

The practical ranking for structs: slices.SortFunc first, sort.Sort close behind (and still the right choice if the type already implements the interface), sort.Slice last, with the advantage of a short call site.

Stability costs more

A stable sort keeps equal elements in the order they arrived. The standard library does it with insertion sort blocks and in place merges, which takes more comparisons. slices.SortStableFunc was 3.5 times slower than the unstable one at 100,000, and sort.SliceStable was 9.8 times slower. The scores here are integers in 0 to 999, so 100 records share each value, and the stability requirement is real: a stable sort would keep records with the same score in their ID order.

Ask whether you need it. Sorting by a total key (ID, a timestamp with a tiebreaker) does not need a stable sort. Sorting a list a user will see by a column with many ties does. The cheapest way to get stable results from the fast sort is to add the original position or ID to the comparison as a tiebreaker:

slices.SortFunc(s, func(a, b rec) int {
	return cmp.Or(cmp.Compare(a.Score, b.Score), cmp.Compare(a.ID, b.ID))
})

cmp.Or (Go 1.22) returns the first non zero result, so ties on score are broken by ID, the result is deterministic, and you pay for one more integer comparison only on ties.

Order in the input

Sorted, reversed and all equal input was 57 to 76 times faster than random. Pattern defeating quicksort scans for runs and recognises the common patterns, so it detects an already ordered or reversed slice in one pass and finishes. This has two consequences. A benchmark that sorts data that is already ordered (for instance, the second iteration of a loop that sorts the same buffer in place) is measuring a different, much faster thing. The lab copies the unsorted source before every iteration for that reason. And re-sorting a slice that is nearly sorted, after appending a few items, is cheap, so do not write special code to avoid it.

Choosing

1. Ordered types (ints, floats, strings): slices.Sort. It beat every alternative and allocates nothing.
2. Structs by a key: slices.SortFunc with cmp.Compare (and cmp.Or for tiebreakers).
3. A type that already has Len/Less/Swap: sort.Sort is fine, and was within 8 percent of slices.SortFunc.
4. Avoid sort.Slice on hot paths. It is the slowest struct sort and the only one that allocates the reflection swapper.
5. Stable only when ties are visible, and prefer a tiebreaker key to a stable sort.
6. Sort once. Sorting a million element slice takes tens of milliseconds, and sorting it in a request handler on every call is the real cost. Keep the sorted result.
7. Check ordering before sorting with slices.IsSorted if the input is often sorted already, though the sort detects it in about a hundredth of the random time.

Checklist

• sort.Ints and slices.Sort are identical in speed since Go 1.22.
• A function based comparison costs 1.5 to 4 times a built in < for ints.
• slices.SortFunc beat sort.Sort and sort.Slice on 32 byte structs.
• Stable sorts cost 3.5 to 10 times more; use a tiebreaker when you can.
• Sorted input is about 75 times cheaper; benchmark with an unsorted copy.

The functions are documented in the slices package and the sort package, and the algorithm is described in the pdqsort paper.