Sorting Slices in Go: Many Ways, Varied Performance

January 16, 2024
Sorting Slices in Go: Many Ways, Varied Performance

There are multiple ways to sort a slice using the sort package and Go 1.21 added even more with it’s generic-powered slices package. If you want to take a look at all of them, or you’ve ever wondered if they are any different in terms of performance (spoiler: they are), then you’re in a good place!

Different ways to sort slices in Go

If you are working with built in types like int, float64 or string, the sort package got you covered. The most straightforward way of sorting such slices is to use the pre-defined functions from that package:

When it comes to the rest of types, you can use sort.Slice function. The first argument needs to be a slice, while the second one is a function that is used for comparing the elements. Arguments to said function are indexes I and j which you use to decide which of the two elements is smaller.

This way is especially useful for one-time operations. If you’re sorting slices of some type more often, or you want to make it easier for others to sort your type, you can consider creating a type for such slice and implementing the sort.Interface.

To do that, you need 3 functions: Len, Swap and Less. The following snippet shows an example of how it could look like:

This actually is exactly how sort.Ints , sort.Float64s and sort.Strings work. Each one of them uses a custom slice type, you can see the implementation of one of them here.

Slices package, introduced in Go 1.21 brings two new ways to sort slices. The function slices.Sort can be used to sort any types that satisfy the constraints.Ordered and their derivatives. So if you want to sort numeric types or strings, this is a good one.

The second function from this package you can use, which might be especially useful for user-defined structures, is slices.SortFunc. It takes any slice as a first argument, while expecting the second one to be a comparison function.

The comparison function also uses generics and expects two arguments of the same type as slice elements. For the sort to work properly, it needs to return a negative number if a is smaller than b, positive number if a is larger than b, and zero if an and b are equal.

At times, you might be able to use a shorter and more straightforward version of this function:

The sort-off

For the purpose of this experiment we’ll going to compare the following functions:

  • sort.Slice
  • sort.Ints (so, basically sort.Sort as well)
  • slices.Sort
  • slices.SortFunc

Each one of them was used to sort slices with 1000, 10 000 and 100 000 elements.

The results went from barely existing at 1000 elements to clearly visible at 10 000. The worst performing one turns out to be sort.Ints which uses the interface. Second best (and worst in this case) is sort.Slice. It looks that the new contestant slices.Sort takes the crown, but…

Is the choice that simple?

So far we’ve only focused on slice’s size, but there’s another factor to consider - the size of a struct. Let’s take another look at the signature of slices.SortFunc :

The important part is the way that elements are being passed for the comparison. Yes, they are copied. Can it significantly impact the performance?

As usual, let’s run some more benchmarks and see the results. The following chart shows how the sorting time was affected by the struct size for a 10 000 elements slice.

Surprised? I must admit that I was not expecting such significant difference.

So, what’s the best choice?

i believe that in most cases, the differences will not be enough to worry about them and prematurely optimize the code, so choose whatever works best for you. However if speed is a crucial factor for your application - the presented benchmarks might give you some idea.

Go