ZetCode

Go sort

last modified October 20, 2020

Go sort tutorial shows how to sort slices and user-defined collections in Golang.

Sorting

Sorting is arranging elements in an ordered sequence. In computer science, many algorithms were developed to perform sorting on data, including merge sort, quick sort, selection sort, or bubble sort. (The other meaning of sorting is categorizing; it is grouping elements with similar properties.)

The opposite of sorting, rearranging a sequence of elements in a random or meaningless order, is called shuffling.

Basic data types can ben sorted in a natural order, either alphabetically or numerically. The sort key specifies the criteria used to perform the sort. We can also sort objects by multiple keys. For instance, when sorting users, the names of the users could be used as primary sort key, and their occupation as the secondary sort key.

Sorting order

A standard order is called the ascending order: a to z, 0 to 9. The reverse order is called the descending order: z to a, 9 to 0. For dates and times, ascending means that earlier values precede later ones e.g. 1/1/2019 will sort ahead of 1/1/2023.

Stable sort

In a stable sorting algorithms, the initial order of equal elements is preserved. Some sorting algorithms are naturally stable, some are not. For example, the bubble sort and the merge sort are stable sorting algorithms. On the other hand, heap sort and quick sort are examples of unstable sorting algorithms.

Consider the following values: 3715593. A stable sorting produces the following: 1335579. The ordering of the values 3 and 5 is kept. An unstable sorting may produce the following: 1335579.

Sorting in Go

Go has the standard sort package for doing sorting. The sorting functions sort data in-place. For basic data types, we have built-in functions such as sort.Ints and sort.Strings. For more complex types, we need to create our own sorting by implementing the sort.Interface:

type Interface interface {
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}

The interface contains three functions: Len, Less, and Swap.

Go sort integers

The sort.Ints sorts a slice of ints in ascending order. The Reverse function returns the reverse order for data.

sort_ints.go
package main

import (
    "fmt"
    "sort"
)

func main() {

    vals := []int{3, 1, 0, 7, 2, 4, 8, 6}
    sort.Ints(vals)
    fmt.Println(vals)

    sort.Sort(sort.Reverse(sort.IntSlice(vals)))
    fmt.Println(vals)
}

The example sorts a slice of integers in ascending and descending order.

$ go run sort_ints.go
[0 1 2 3 4 6 7 8]
[8 7 6 4 3 2 1 0]

This is the output.

Go sort strings

The sort.Strings sorts a slice of strings in ascending order.

sort_strings.go
package main

import (
    "fmt"
    "sort"
)

func main() {

    words := []string{"bear", "atom", "world", "falcon", "cloud", "forest"}

    sort.Strings(words)
    fmt.Println(words)

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

We have a slice of words. We sort the words in ascending and descending orders.

sort.Strings(words)

The sort.Strings sorts the words in ascending order.

sort.Sort(sort.Reverse(sort.StringSlice(words)))

With the help of the sort.Reverse and sort.StringSlice functions, we sort the words in descending order.

$ go run sort_strings.go
[atom bear cloud falcon forest world]
[world forest falcon cloud bear atom]

This is the output.

Go check sorting

We can check if the data is sorted with sort.StringsAreSorted, sort.IntsAreSorted, or sort.SliceIsSorted functions.

check_sorting.go
package main

import (
    "fmt"
    "sort"
)

func main() {

    words := []string{"bear", "atom", "world", "falcon", "cloud", "forest"}

    sorted := sort.StringsAreSorted(words)
    fmt.Println(sorted)

    sort.Sort(sort.StringSlice(words))

    sorted = sort.StringsAreSorted(words)
    fmt.Println(sorted)

    // --------------------------------------------

    vals := []int{5, 2, 6, 3, 1, 7, 8, 4, 0}

    sorted = sort.IntsAreSorted(vals)
    fmt.Println(sorted)

    sort.Ints(vals)

    sorted = sort.IntsAreSorted(vals)
    fmt.Println(sorted)
}

In the example, we check if our two slices are sorted.

$ go run check_sorting.go
false
true
false
true

This is the output.

Go custom sorting

For custom sorting we need to implement the sort.Interface functions.

custom_sorting.go
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{"cloud", "atom", "sea", "by", "forest", "maintenance"}
    sort.Sort(ByLength(words))
    fmt.Println(words)
}

In the example, we sort a slice of words by their length.

type ByLength []string

We create a custom type ByLength, which is an alias for the built-in []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])
}

We implement the three functions required by the sorting interface.

sort.Sort(ByLength(words))

We cast the slice of string words to our type and we call the Sort function on that typed slice.

$ go run custom_sorting.go
[by sea atom cloud forest maintenance]

The words are sorted by their length in ascending order.

Go sort.Slice

The sort.Slice is a convenience function to sort data in a slice without having to create custom types.

slice_fun.go
package main

import (
    "fmt"
    "sort"
)

func main() {

    words := []string{"cloud", "atom", "sea", "by", "forest", "maintenance"}

    sort.Slice(words, func(i1, i2 int) bool {
        return len(words[i1]) < len(words[i2])
    })

    fmt.Println(words)

    sort.Slice(words, func(i1, i2 int) bool {
        return len(words[i1]) > len(words[i2])
    })

    fmt.Println(words)
}

We sort the slice of words by their length. We pass an anonymous comparison function to sort.Slice.

$ go run slice_fun.go
[by sea atom cloud forest maintenance]
[maintenance forest cloud atom sea by]

This is the output.

Go sort map by keys

In the following examples, we sort a map by keys.

sort_map_keys.go
package main

import (
    "fmt"
    "sort"
)

func main() {

    items := map[string]int{
        "coin":   12,
        "chair":  3,
        "pen":    4,
        "bottle": 9,
    }

    keys := make([]string, 0, len(items))

    for key := range items {
        keys = append(keys, key)
    }

    sort.Strings(keys)

    for _, key := range keys {
        fmt.Printf("%s %d\n", key, items[key])
    }
}

In order to sort a map by its keys, we pick the keys into a keys slice, sort them, and finally pick values using this sorted slice.

$ go run sort_map_keys.go 
bottle 9
chair 3
coin 12
pen 4    

This is the output.

Go sort structs

In the following example, we sort a list of structures.

sort_struct.go
package main

import (
    "fmt"
    "sort"
)

type Student struct {
    name  string
    score int
}

func main() {

    students := []Student{

        Student{name: "John", score: 45},
        Student{name: "Bill", score: 68},
        Student{name: "Sam", score: 98},
        Student{name: "Julia", score: 87},
        Student{name: "Tom", score: 91},
        Student{name: "Martin", score: 71},
    }

    sort.Slice(students, func(i, j int) bool {
        return students[i].score < students[j].score
    })

    fmt.Println(students)

    sort.Slice(students, func(i, j int) bool {
        return students[i].name > students[j].name
    })

    fmt.Println(students)
}

We have a slice of student objects, created from the Student struct. We provide two anonymous functions to the sort.Slice to sort the slice by scores and names.

$ go run sort_struct.go 
[{John 45} {Bill 68} {Martin 71} {Julia 87} {Tom 91} {Sam 98}]
[{Tom 91} {Sam 98} {Martin 71} {Julia 87} {John 45} {Bill 68}]

This is the output.

Go sort by multiple fields

Data can be sorted by multiple criteria.

sort_mul_fields.go
package main

import (
    "fmt"
    "sort"
)

type Student struct {
    name  string
    score int
}

func main() {

    students := []Student{

        Student{name: "John", score: 87},
        Student{name: "Albert", score: 68},
        Student{name: "Bill", score: 68},
        Student{name: "Sam", score: 98},
        Student{name: "Xenia", score: 87},
        Student{name: "Lucia", score: 87},
        Student{name: "Tom", score: 91},
        Student{name: "Jane", score: 68},
        Student{name: "Martin", score: 71},
        Student{name: "Julia", score: 87},
    }

    sort.Slice(students, func(i, j int) bool {

        if students[i].score != students[j].score {
            return students[i].score < students[j].score
        }

        return students[i].name < students[j].name
    })

    fmt.Println(students)
}

In the example, we sort a slice of students by score and when the score is the same, by name.

sort.Slice(students, func(i, j int) bool {

    if students[i].score != students[j].score {
        return students[i].score < students[j].score
    }

    return students[i].name < students[j].name
})

The sorting logic is implemented in the anonymous function. First, we compare the scores. Then, if the score is identical, we compare the names.

$ go run sort_mul_fields.go 
[{Albert 68} {Bill 68} {Jane 68} {Martin 71} {John 87} {Julia 87} 
    {Lucia 87} {Xenia 87} {Tom 91} {Sam 98}]

This is the output.

Go sort by datetime

In the following example, we sort data by datetime.

sort_date_time.go
package main

import (
    "fmt"
    "sort"
    "time"
)

type Purchase struct {
    id   string
    date time.Time
}

func main() {

    var purchases = make([]Purchase, 0)
    purchases = append(purchases, Purchase{id: "1", date: time.Now()})
    purchases = append(purchases, Purchase{id: "2", date: time.Now().AddDate(-3, 0, 7)})
    purchases = append(purchases, Purchase{id: "3", date: time.Now().AddDate(2, 4, 7)})
    purchases = append(purchases, Purchase{id: "4", 
        date: time.Now().AddDate(-5, -5, -7)})

    sort.Slice(purchases, func(i, j int) bool {
        return purchases[i].date.Before(purchases[j].date)
    })

    for _, pur := range purchases {

        fmt.Printf("%s %s\n", pur.id, pur.date.Format("2 Jan 2006 15:04"))
    }
}

We have a slice of purchases. The purchases are sorted by their datetimes.

sort.Slice(purchases, func(i, j int) bool {
    return purchases[i].date.Before(purchases[j].date)
})

In the comparison function, we use the Before function to figure out whether the first time is before the second.

$ go run sort_date_time.go 
4 13 May 2015 14:42
2 27 Oct 2017 14:42
1 20 Oct 2020 14:42
3 27 Feb 2023 14:42

This is the output.

In this tutorial, we have sorted data in Golang.

List all Go tutorials.