How to use the new package in Go standard library to sort slices efficiently.
With the release of Go 1.21, the Go standard library introduced several new
features. While we’ve already discussed some of them in previous articles, in this
episode, we’ll dive into more advanced enhancements. Naturally, we’ll focus on the new functions designed for sorting
slices, which are part of the new slices package. This article will provide a
deeper look into the implementation of these three new functions and touch on benchmarking as well.
The Sort function is the first one we’d like to explore. This implementation is built upon the enhanced
Pattern-defeating Quicksort, positioning
it as one of the best-known unstable sorting algorithms. Don’t worry; we will discuss this “instability” aspect in this
article. But first, let’s take a look at the function’s signature:
As we’ve seen in some other articles, nearly all improvements in the Go standard library
are built upon generics, a feature introduced in Go version 1.18, almost
three years ago. Similar to other functions, the Sort function also expects a slice of a generic type as an argument,
where each item must adhere to the Ordered
constraint. The function doesn’t return a new value but sorts the original slice in place. Below, you’ll find some basic
In the example above, we can observe the result of the Sort method. All the outputs consist of sorted slices, arranged
in ascending order. However, what makes this function particularly intriguing is its ability to handle various data types
using a single function, distinguishing it from the implementations we already possess in the sort
package. Now that we’ve examined the results, let’s proceed to compare the performance benchmarks with the existing package.
In this section, we aim to evaluate the performance of the new function by comparing it to the already existing sort
package. Below, you’ll find the benchmark test results:
First and foremost, we need to create our test cases, as shown in the example above. Here, we provide three functions for
generating test cases: one with randomly distributed integers in slices, another with already sorted slices, and a third
with reversely sorted slices. It’s crucial to note that before the tests begin, we generate all the test cases. That’s
why we execute anonymous functions and store their results in global variables: randomInts, sortedInts, and reversedInts
right at the start. By creating these test cases in the beginning, we ensure that our tests use the same predefined cases.
You can find the actual test results below:
You can observe the benchmarking results in the code above. In each iteration of the benchmarks, we used the test cases
generated at the beginning of the test. However, we ensured to create clones of these test cases to prevent modifying the
original ones, as all Sort functions work with slices by reference and modify the originals.
The outcome shows that, across all three groups of cases, the sorting solution from the new slices package is remarkably
2.5 times faster than the existing solution from the sort package. Personally, while I was hopeful for improved
benchmarking in the new package, I didn’t anticipate such significantly better performance compared to the sort package.
SortFunc and SortStableFunc
In this section, we will explore the SortFunc function and delve into the concept of instability introduced by this
package. Before we proceed with the explanation, let’s take a look at the function’s signature:
funcSortFunc[S~E, Eany](xS, cmpfunc(a, bE) int)
Similar to previous examples, the purpose of SortFunc here is to sort slices that may contain items of any type, not
necessarily belonging to the Ordered constraint. However, it’s precisely in these scenarios, where we introduce sorting
for more complex types, that we may encounter some instability, as demonstrated below:
In the example above, we introduce a custom struct named TestStruct (quite unexpected, right?). It has two attributes:
Value, which we’ll use in the comparison function to determine the item’s position in the sorted slice, and Name,
which serves as a description for tracking items’ positions in the slice after sorting, without influencing the sorting
For our test data, we’ve created a slice comprising fifteen items (to reveal instability, a slice should have at least
13 items). In this slice, we have three groups of values (1, 2, and 3) with item names uniquely derived from
ordered numbers (first to fifteenth). What were the results of execution? The sorting process consistently produced
the correctly sorted slice, maintaining the same order of items. However, items that were supposed to change their positions
during sorting didn’t preserve their initial order when their values were identical.
For instance, the item named sixth now appears as the second item, right after the tenth item. However, originally,
sixth was added to the original slice before tenth. This exemplifies a critical aspect of instability introduced by
SortFunc: it doesn’t randomly rearrange identical items with each execution. Instead, one slice will consistently have
the same order after sorting, but SortFunc doesn’t guarantee that identical items will retain their original ordering.
To explore how we can address this issue, let’s take a look at the signature of another function:
In this instance, the concept of stability becomes quite evident. Concerning values, the SortStableFunc function also
arranges items with the value 0 five times, followed by five occurrences of the value 1, and finally, five instances
of the value 2. However, what distinguishes this function is that elements with the same value maintain the same order
established during the initialization of the slice. With this function, we can anticipate the order of identical elements.
But, are there any consequences to consider? Let’s revisit the benchmark to find out.
To compare the performance of both functions, we’ll use the same setup as in the previous benchmark:
The outcome we observed shouldn’t come as a big surprise, right? After all, why would we need unstable sorting in the
first place? As seen in the benchmark results, the efficiency of unstable sorting varies depending on the case, ranging
from 50% faster than the stable variant to over 10 times faster! This vividly highlights the significance of having both
stable and unstable versions of the function. It also provides us with guidance on how to proceed with these functions:
always opt for the unstable one if you aren’t particularly concerned about the order of identical elements.
New version of Golang, 1.21, delivered many new updates, affecting standard library as well. In this article we checked
how some functions from slices packages work. Those new functions give us now possibility to more efficiently sort
slices than ever before, by using the modern algorithms.