Telusko Docs

Sorting in Go went through a real change. For a decade the answer was the sort package, with its interface of three methods and its sort.Slice closure. Then Go 1.21 added the generic slices package, and most sorting code got shorter and faster at the same time.

You need to recognise both, because existing codebases are full of the old style. You should write the new one.

The modern way

import "slices"

nums := []int{5, 2, 9, 1, 7}
slices.Sort(nums)
fmt.Println(nums)              // [1 2 5 7 9]

names := []string{"zoya", "arjun", "meera"}
slices.Sort(names)             // [arjun meera zoya]

slices.Sort works on any slice whose element type is ordered, which covers every numeric type plus string. No interface, no closure, and because it is generic the comparison is inlined rather than going through a function call per element.

Sorting by a field

type Person struct {
    Name string
    Age  int
}

people := []Person{
    {"Shiva", 28},
    {"Navin", 41},
    {"Hyder", 35},
}

slices.SortFunc(people, func(a, b Person) int {
    return cmp.Compare(a.Age, b.Age)
})

The comparison function returns a negative number, zero, or a positive number, the same convention as C's qsort and Java's Comparator. cmp.Compare from the cmp package does that for any ordered type, so you rarely write the subtraction yourself.

Descending order is a matter of swapping the arguments:

slices.SortFunc(people, func(a, b Person) int {
    return cmp.Compare(b.Age, a.Age)      // b first
})

Multiple sort keys

cmp.Or returns the first non-zero value, which makes tie-breaking read cleanly:

slices.SortFunc(people, func(a, b Person) int {
    return cmp.Or(
        cmp.Compare(a.Department, b.Department),
        cmp.Compare(b.Age, a.Age),          // within a department, oldest first
        cmp.Compare(a.Name, b.Name),        // then alphabetical
    )
})

Three keys, three lines, and the priority order is exactly the reading order.

Keeping equal elements in place

slices.Sort is not stable, meaning elements that compare equal may end up in any relative order. When that matters:

slices.SortStableFunc(people, func(a, b Person) int {
    return cmp.Compare(a.Department, b.Department)
})

Stability costs a little performance, so it is a separate function rather than the default. You need it when you sort by one key after having already sorted by another.

The older way, which you will still read

import "sort"

// Sorting a slice with a less function
sort.Slice(people, func(i, j int) bool {
    return people[i].Age < people[j].Age
})

// Convenience wrappers for basic types
sort.Ints(nums)
sort.Strings(names)
sort.Float64s(values)

// Checking
sort.IntsAreSorted(nums)

Note the different comparison shape. sort.Slice takes indexes and returns a boolean meaning "i comes before j", where slices.SortFunc takes values and returns a three-way integer.

sort.Slice uses reflection internally to swap elements, which makes it noticeably slower than the generic version. Benchmarks typically show slices.SortFunc at around twice the speed. If you are on Go 1.21 or later, there is no reason to write new code with sort.Slice.

The sort.Interface form

The oldest style implements three methods:

type ByAge []Person

func (a ByAge) Len() int           { return len(a) }
func (a ByAge) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }

sort.Sort(ByAge(people))

Verbose, but it makes sorting a first class property of a type, and it is what sort.Sort and sort.Stable accept. You will find it in older libraries and occasionally where a type has one obvious natural ordering.

Searching

Binary search

On a sorted slice, binary search finds an element in logarithmic time:

nums := []int{1, 3, 5, 7, 9, 11}

i, found := slices.BinarySearch(nums, 7)
fmt.Println(i, found)        // 3 true

i, found = slices.BinarySearch(nums, 8)
fmt.Println(i, found)        // 4 false, but 4 is where 8 would go

That insertion index is genuinely useful. When the value is absent, you get the position to insert it while keeping the slice sorted:

if !found {
    nums = slices.Insert(nums, i, 8)
}

For custom types:

i, found := slices.BinarySearchFunc(people, target, func(p, t Person) int {
    return cmp.Compare(p.Age, t.Age)
})

Binary search on an unsorted slice does not error, it returns nonsense. There is no check, because checking would cost as much as the search. Sort first, or maintain the ordering as you insert.

Linear search

For small slices or unsorted data:

i := slices.Index(nums, 7)                 // -1 if absent
ok := slices.Contains(nums, 7)

i = slices.IndexFunc(people, func(p Person) bool {
    return p.Name == "Shiva"
})

ok = slices.ContainsFunc(people, func(p Person) bool {
    return p.Age > 40
})

The crossover point where binary search starts winning is somewhere around fifty to a hundred elements, and it depends on how expensive the comparison is. Below that, a linear scan over contiguous memory is often faster in practice because it is cache friendly and has no branching overhead.

For repeated lookups by key, neither is right. Build a map once:

byID := make(map[int]Person, len(people))
for _, p := range people {
    byID[p.ID] = p
}

p, ok := byID[42]

One pass to build, constant time per lookup afterwards.

Sorting a map

Maps have no order, so you sort a slice derived from them.

scores := map[string]int{
    "shiva": 92,
    "navin": 88,
    "hyder": 95,
}

// By key
keys := slices.Sorted(maps.Keys(scores))
for _, k := range keys {
    fmt.Printf("%s: %d\n", k, scores[k])
}

// By value
type entry struct {
    Name  string
    Score int
}

entries := make([]entry, 0, len(scores))
for k, v := range scores {
    entries = append(entries, entry{k, v})
}
slices.SortFunc(entries, func(a, b entry) int {
    return cmp.Compare(b.Score, a.Score)      // highest first
})

That second pattern, flattening a map into a slice of structs to sort it, is common enough that it is worth having in your fingers.

The rest of the slices package

Go 1.21 brought more than sorting, and these functions replace a lot of hand-written loops:

slices.Reverse(s)
slices.Clone(s)                       // an independent copy
slices.Equal(a, b)                    // element by element
slices.Max(s)
slices.Min(s)
slices.Compact(s)                     // remove consecutive duplicates
slices.Insert(s, i, values...)
slices.Delete(s, i, j)
slices.IsSorted(s)

slices.Compact pairs naturally with sorting to deduplicate:

slices.Sort(items)
items = slices.Compact(items)         // only removes adjacent duplicates

Sorting first is what makes all duplicates adjacent. Without it, Compact only collapses runs that happened to be next to each other.

Which algorithm Go uses

slices.Sort uses pattern-defeating quicksort, usually written pdqsort. It is a hybrid: quicksort in the general case, insertion sort for small partitions, and heapsort as a fallback when the recursion gets too deep. That last part matters, because it means the worst case is O(n log n) rather than quicksort's usual O(n squared).

slices.SortStableFunc uses an in-place merge sort, which is why it is stable and slightly slower.

You do not need to think about any of this. It is worth knowing only so that the answer to "should I write my own quicksort" is confidently no.

A worked example

Taking a slice of records through the whole pipeline:

type Order struct {
    ID       int
    Customer string
    Total    int64
    Placed   time.Time
}

func topCustomers(orders []Order, n int) []string {
    // Aggregate by customer
    totals := make(map[string]int64)
    for _, o := range orders {
        totals[o.Customer] += o.Total
    }

    // Flatten into something sortable
    type row struct {
        Customer string
        Total    int64
    }
    rows := make([]row, 0, len(totals))
    for c, t := range totals {
        rows = append(rows, row{c, t})
    }

    // Highest spend first, ties broken alphabetically for a stable result
    slices.SortFunc(rows, func(a, b row) int {
        return cmp.Or(
            cmp.Compare(b.Total, a.Total),
            cmp.Compare(a.Customer, b.Customer),
        )
    })

    // Take the top n
    if len(rows) > n {
        rows = rows[:n]
    }

    names := make([]string, len(rows))
    for i, r := range rows {
        names[i] = r.Customer
    }
    return names
}

Grouping with a map, flattening into a slice, sorting with a tie-break, truncating, and projecting. Every step uses something from this section, and none of it needs a library.

That covers Go's collections. Next, let's define our own types, which is where the language starts to feel like yours rather than the standard library's.

Sorting and Searching