Good evening

Even though sorting in Golang is discussed in documentation, it took me a while to notice the examples there. By the time I found them, I had already figured it out myself. Not to mention that they can look a bit overwhelming for such a simple task.

This article is simply a quick recipe for sorting of custom structures in go.

Consider you have a structure that has an integer myInt and a boolean myBool (and maybe something else). You have a slice of these structures (or pointers to them, which is essentially equivalent) and you want it to be sorted by myInt. If two elements have the same myInt, the one with myBool set to false should come first (it is somewhat similar to Python behavior, where True>False is a valid expression resolving to True).

There are functions such as sort and stable that take an argument with the type Interface and perform an in-place sorting. As you can see in the documentation, the passed argument should have three methods defined: Len, Swap and Less. They are self-explanatory: Len defines how you determine the length of your slice, Swap switches two elements, and Less returns true if the first argument is, according to our logic, has a lower (but not equal) value compared to the second one. Some libraries in other languages ask for a function that returns -1 if the value is lower, 0 if equal and 1 if higher, but that is not needed here.

So here’s the code.

package main

import (
	"fmt"
	"sort"
)

type MyObject struct {
	myInt  int64
	myBool bool
}

type MyObjectSortMyintMybool []*MyObject //sortable type

func MySort(src []*MyObject) {
	sort.Sort(MyObjectSortMyintMybool(src))
}

func main() {
	src := []*MyObject{{1, true}, {3, true}, {2, false}, {1, false}, {3, false}, {2, true}}

	MySort(src)

	for _, v := range src {
		fmt.Println(v)
	}
}

func (ps MyObjectSortMyintMybool) Len() int      { return len(ps) }
func (ps MyObjectSortMyintMybool) Swap(i, j int) { ps[i], ps[j] = ps[j], ps[i] }
func (ps MyObjectSortMyintMybool) Less(i, j int) bool {
	if ps[i].myInt == ps[j].myInt {
		return !ps[i].myBool && ps[j].myBool //it's not Python! You cannot compare booleans in Golang directly!
	}
	return ps[i].myInt < ps[j].myInt
}

We had to define a new type MyObjectSortMyintMybool based on our slice, and set the aforementioned methods to it. Since you may want to sort your structures by different logic in various parts of your program, you need to define a new type for every sorting logic. Then you can just convert the type right before passing it to the sorting function.

The result is:

&{1 false}
&{1 true}
&{2 false}
&{2 true}
&{3 false}
&{3 true}

A slightly more compact way

I noticed later that there is a Slice function that takes a slice and a less function directly. Here’s what the code looks like if we use it.

package main

import (
	"fmt"
	"sort"
)

type MyObject struct {
	myInt  int64
	myBool bool
}

func MySort(src []*MyObject) {
	sort.Slice(src, func(i, j int) bool {
		if src[i].myInt == src[j].myInt {
			return !src[i].myBool && src[j].myBool //it's not Python! You cannot compare booleans in Golang directly!
		}
		return src[i].myInt < src[j].myInt
	})
}

func main() {
	src := []*MyObject{{1, true}, {3, true}, {2, false}, {1, false}, {3, false}, {2, true}}

	MySort(src)

	for _, v := range src {
		fmt.Println(v)
	}
}

This way you can define the comparison logic right where the sorting takes place, and you don’t need a new type.

Benchmarks

The only thing that bothered me about Slice was that, according to source, it uses reflect, which tends to slow the program down. So I ran a simple benchmark for both programs. Here is its code:

package main

import "testing"

func BenchmarkMySort(b *testing.B) {

	for n := 0; n < b.N; n++ {
		src := []*MyObject{{1, true}, {3, true}, {2, false}, {1, false}, {3, false}, {2, true}}

		MySort(src)
	}
}

For reference: if your file is called mysort.go, the benchmark code should be put in mysort_test.gofile. Then you run go test -bench=.

I have put src allocation into every iteration because the sorting is in-place. It modifies the initial slice, so we have to reinitialize it every time.

The result for the first recipe was around 300 ns/op, while the result for the second one was approximately 350 ns/op. The more elegant brief example is a tiny bit slower than the bloated one.

But wait, we have a slice of only 6 elements. What if we take a much much bigger one? Like, tens of thousands?

Here’s another benchmark where I allocate a slice of 60 thousand elements.

package main

import "testing"

const COPIES = 10000

func BenchmarkMySort(b *testing.B) {
	sample := []*MyObject{{1, true}, {3, true}, {2, false}, {1, false}, {3, false}, {2, true}}
	src := make([]*MyObject, 0, len(sample)*COPIES)
	for i := 0; i < COPIES; i++ {
		src = append(src, sample...)
	}

	for n := 0; n < b.N; n++ {
		lsrc := make([]*MyObject, len(sample)*COPIES)
		copy(lsrc, src)
		MySort(lsrc)
	}
}

The results are 1.80 and 1.65 milliseconds per operation respectively. So the second one is now slightly faster instead. Not sure why the results swapped, but at least the reflect overhead becomes insignificant on bigger arrays.

In conclusion

So there you have it. Two ways to sort a slice. The second way is superior in most ways: it is slightly faster on bigger arrays and more readable. Since I consider Golang to be a language for business, readability is a priority most of the time.

The first example is useful in exotic situations when you call Sort thousands and thousands of times on small slices and the performance gain of even 15% is crucial. Or if you want to add something to the swapping mechanism, like logging or tracking of original locations.

Thanks for reading and Happy New Year!