BrevFeed
Sign in

56. Sorting and searching

📖 Reading · 12 min
💡 Most code boxes below are live — edit one and hit Run. Boxes without a Run button are reference-only (they can't run in your browser).

Sorting comes up constantly — and in Go it's almost always one line. This lesson covers the sort package you'll see in every codebase, plus the newer generic slices package that's replacing it.

The one-liners

package main

import (
    "fmt"
    "sort"
)

func main() {
    nums := []int{5, 2, 8, 1, 9}
    words := []string{"banana", "apple", "cherry"}
    prices := []float64{9.99, 2.50, 19.95}

    sort.Ints(nums)
    sort.Strings(words)
    sort.Float64s(prices)

    fmt.Println(nums)
    fmt.Println(words)
    fmt.Println(prices)

    fmt.Println(sort.IntsAreSorted(nums))
}

All three sort in place — they modify the slice and return nothing. If you need the original order preserved, copy first (module 4).

sort.Slice — sort anything by anything

The workhorse. You supply a less function and it does the rest:

package main

import (
    "fmt"
    "sort"
)

type Person struct {
    Name string
    Age  int
    City string
}

func main() {
    people := []Person{
        {"Ada", 36, "London"},
        {"Grace", 45, "Arlington"},
        {"Alan", 41, "London"},
        {"Katherine", 45, "Hampton"},
    }

    sort.Slice(people, func(i, j int) bool {
        return people[i].Age < people[j].Age
    })
    fmt.Println("by age:")
    for _, p := range people {
        fmt.Printf("  %-10s %d\n", p.Name, p.Age)
    }

    sort.Slice(people, func(i, j int) bool {
        if people[i].Age != people[j].Age {
            return people[i].Age > people[j].Age
        }
        return people[i].Name < people[j].Name
    })
    fmt.Println("by age desc, then name:")
    for _, p := range people {
        fmt.Printf("  %-10s %d\n", p.Name, p.Age)
    }
}

The less(i, j) function answers one question: should element i come before element j? Everything follows from that:

  • ascending: a[i] < a[j]
  • descending: a[i] > a[j]
  • multi-key: compare the primary key, and only fall through to the secondary when the primary is equal — exactly the shape in the second sort above.

Stable vs unstable

package main

import (
    "fmt"
    "sort"
)

type Entry struct {
    Group string
    Order int
}

func main() {
    entries := []Entry{
        {"b", 1}, {"a", 2}, {"b", 3}, {"a", 4}, {"c", 5},
    }

    sort.SliceStable(entries, func(i, j int) bool {
        return entries[i].Group < entries[j].Group
    })

    for _, e := range entries {
        fmt.Printf("%s%d ", e.Group, e.Order)
    }
    fmt.Println()
    fmt.Println("within each group, original order is preserved")
}

sort.Slice uses an introsort variant that is not stable — equal elements can be reordered. sort.SliceStable preserves their relative order, at a small cost.

Use SliceStable when you sort by one key after already sorting by another, which is how you build multi-level sorts incrementally.

Sorting map contents

Maps have no order, so the recipe from module 4 shows up again:

package main

import (
    "fmt"
    "sort"
)

func main() {
    votes := map[string]int{
        "go": 42, "rust": 37, "zig": 12, "c": 42,
    }

    names := make([]string, 0, len(votes))
    for name := range votes {
        names = append(names, name)
    }

    sort.Slice(names, func(i, j int) bool {
        if votes[names[i]] != votes[names[j]] {
            return votes[names[i]] > votes[names[j]]
        }
        return names[i] < names[j]
    })

    for i, name := range names {
        fmt.Printf("%d. %-5s %d\n", i+1, name, votes[name])
    }
}

Collect keys → sort them with a comparator that looks up the map → iterate. Note the tie-break on name: without it, go and c (both 42) would come out in an arbitrary order, and your output would differ between runs.

Always break ties on something deterministic when the output is a report, a test fixture, or anything a human will diff.

Binary search

Once a slice is sorted, sort.Search finds things in O(log n):

package main

import (
    "fmt"
    "sort"
)

func main() {
    nums := []int{1, 3, 5, 7, 9, 11}

    i := sort.SearchInts(nums, 7)
    fmt.Println("index of 7:", i)

    j := sort.SearchInts(nums, 8)
    fmt.Println("8 would be inserted at:", j, "- present:", j < len(nums) && nums[j] == 8)

    k := sort.Search(len(nums), func(i int) bool { return nums[i] >= 6 })
    fmt.Println("first element >= 6 is at index", k, "->", nums[k])
}

sort.Search is more general than it first looks: it returns the smallest index for which the function is true, assuming the function goes false → true exactly once across the slice. That makes it a tool for any monotonic predicate, not just equality.

Note the "present" check: search functions return an insertion point, so you must verify the element at that index is actually what you wanted.

sort.Interface, for completeness

The original mechanism, from module 6:

package main

import (
    "fmt"
    "sort"
)

type ByLength []string

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

func main() {
    words := []string{"banana", "fig", "apple", "kiwi"}

    sort.Sort(ByLength(words))
    fmt.Println(words)

    sort.Sort(sort.Reverse(ByLength(words)))
    fmt.Println(words)
}

Three methods and you can sort with sort.Sort. The payoff is sort.Reverse, which wraps any sort.Interface and flips its Less — a neat demonstration of interfaces composing.

For new code, sort.Slice with an inline function is shorter and just as fast. Learn sort.Interface because you'll read it.

The modern way: slices

Go 1.21 added generic versions that are shorter still:

import "slices"

nums := []int{5, 2, 8}
slices.Sort(nums)                    // [2 5 8], no sort.Ints needed

people := []Person{...}
slices.SortFunc(people, func(a, b Person) int {
    return cmp.Compare(a.Age, b.Age)   // -1, 0 or +1
})

i, found := slices.BinarySearch(nums, 5)
slices.Contains(nums, 8)
slices.Index(nums, 2)
slices.Reverse(nums)
slices.Max(nums)

Two differences worth noting: SortFunc takes a three-way comparison (negative / zero / positive, like C's strcmp) rather than a boolean less, and BinarySearch returns (index, found) so you don't have to check yourself.

New code should prefer slices. sort isn't deprecated and isn't going anywhere — you'll see both for years.

(That box is reference-only: the slices package is newer than the interpreter running these lessons.)

Your turn

Sort the products by price descending, breaking ties by name ascending, and print them:

Chair 199.50
Monitor 199.50
Keyboard 49.99

package main

import (
    "fmt"
    "sort"
)

type Product struct {
    Name  string
    Price float64
}

func main() {
    products := []Product{
        {"Keyboard", 49.99},
        {"Monitor", 199.50},
        {"Chair", 199.50},
    }

    // sort by price descending, then name ascending

    for _, p := range products {
        fmt.Printf("%s %.2f\n", p.Name, p.Price)
    }
}

package main

import (
    "fmt"
    "sort"
)

type Product struct {
    Name  string
    Price float64
}

func main() {
    products := []Product{
        {"Keyboard", 49.99},
        {"Monitor", 199.50},
        {"Chair", 199.50},
    }

    sort.Slice(products, func(i, j int) bool {
        if products[i].Price != products[j].Price {
            return products[i].Price > products[j].Price
        }
        return products[i].Name < products[j].Name
    })

    for _, p := range products {
        fmt.Printf("%s %.2f\n", p.Name, p.Price)
    }
}

Chair and Monitor are tied on price, so the second clause decides, and C sorts before M. Being able to predict a comparator's output exactly — including the ties — is the skill this lesson is really teaching.

Next: reading and writing streams.

← Previous Next →