In this blog, we’re going to write some sorting codes with Go.

Overview

Plenty of times, we want to sort a collection (slice of array) of data, for example: we want to sort a slice of orders by its amount, or sort a slice of users by its name.

Go developers will always depend on sort package. https://pkg.go.dev/sort

This sort package contains a lots of functions for us to use. But, the problem with this package is, this package assumes there’s no generics (before Go 1.18), that’s the reason why, each data type (int, float64 and string) has different methods.

In production, we should just use that package, but in this article, we’re going to demonstrate the generics capability to sort various data types.

Starting with the sort Package

Let’s say we have 10 integers and strings data:

ints := []int{27, 4, 2, 5, 3, 1, 8, 11, 19, 28}

strings := []string{"Manila", "New Delhi", "Tokyo", "Bangkok", "London", "Jakarta", "Paris", "Berlin", "Washington DC", "Brisbane"}

users := []User{
    {Name: "John Doe", Age: 25},
    {Name: "Budi", Age: 30},
    {Name: "Rahul", Age: 29},
    {Name: "Carlos", Age: 31},
} // we want to sort users by age

We want to sort these data using sort package. It’s very easy.

package main

import (
	"fmt"
	"sort"
)

type User struct {
	Name string
	Age  int8
}

func main() {
	ints := []int{27, 4, 2, 5, 3, 1, 8, 11, 19, 28}
	strings := []string{"Manila", "New Delhi", "Tokyo", "Bangkok", "London", "Jakarta", "Paris", "Berlin", "Washington DC", "Brisbane"}
	users := []User{
		{Name: "John Doe", Age: 25},
		{Name: "Budi", Age: 30},
		{Name: "Rahul", Age: 29},
		{Name: "Carlos", Age: 31},
	} // we want to sort users by age

	sort.Ints(ints)
	sort.Strings(strings)
	sort.Slice(users, func(i, j int) bool {
		return int(users[i].Age) < int(users[j].Age)
	})

	fmt.Println(ints)
	fmt.Println(strings)
	fmt.Println(users)
}

Output:

[1 2 3 4 5 8 11 19 27 28]
[Bangkok Berlin Brisbane Jakarta London Manila New Delhi Paris Tokyo Washington DC]
[{John Doe 25} {Rahul 29} {Budi 30} {Carlos 31}]

Simplest Sort Algorithm

There are a dozen of sorting algorithm, but we’re going to use the simplest one. The bubble sort. We’re not going to take a scenic route by explaining each sorting algorithm, this article is not about sorting algorithm, but more about generics usage. We’re just going to copy paste from here: https://rosettacode.org/wiki/Sorting_algorithms/Bubble_sort#Go. As we can see there, at the time of writing this article, the Go implementation for sorting is like this:

func bubblesort(a []int) {
    for itemCount := len(a) - 1; ; itemCount-- {
        hasChanged := false
        for index := 0; index < itemCount; index++ {
            if a[index] > a[index+1] {
                a[index], a[index+1] = a[index+1], a[index]
                hasChanged = true
            }
        }
        if hasChanged == false {
            break
        }
    }
}

Right away, we can notice the parameter: []int. This function needs to be duplicated and adjusted if we want to sort a float64 slice. Let’s enhance this function with generics, so that it can receive multiple data type parameters.

func bubblesort[T constraints.Ordered](a []T) {
	for itemCount := len(a) - 1; ; itemCount-- {
		hasChanged := false
		for index := 0; index < itemCount; index++ {
			if a[index] > a[index+1] {
				a[index], a[index+1] = a[index+1], a[index]
				hasChanged = true
			}
		}
		if hasChanged == false {
			break
		}
	}
}

We might be wondering, why changing the type parameter to constraints.Ordered the compiler doesn’t complain about > operation?. Here’s documentation about constraints.Ordered:

Ordered is a constraint that permits any ordered type: any type that supports the operators < <= >= >. If future releases of Go add new ordered types, this constraint will be modified to include them.

Here’s what constraints.Order look like:

type Ordered interface {
    Integer | Float | ~string
}

Reference: https://pkg.go.dev/golang.org/x/exp/constraints#Ordered

That tilde (~) operator means approximation, so that we can pass data type like type MyCustomString string to it.

Moving on, here’s how we call bubblesort:

	floats := []float64{8.9, 90.0, 1.12, 14.13}
	bubblesort(floats)
	fmt.Println(floats)

	strings2 := []string{"Kuala Lumpur", "Canberra", "Istanbul", "Madrid", "Seoul", "New York"}
	bubblesort(strings2)
	fmt.Println(strings2)

Output will be:

[1.12 8.9 14.13 90]
[Canberra Istanbul Kuala Lumpur Madrid New York Seoul]

But how do we call bubblesort[T constraints.Ordered](a []T) with a slice of structs data? This will be discussed in the next article.