All that's a bit vague, and micro-benchmarks are a silly thing to optimize for. But unless someone comes up with a diverse set of benchmarks in multiple languages, we're going to have to live with it. The Go compiler is getting better, and Go has advantages other than speed.

Performance depends as much on the choice and implementation of an algorithm as on the language or runtime.

I looked at the performance of Go's

`Sort`

function. Instead of comparing it to other sort functions or those in other languages, I looked at how its performance depends on its input. For instance, *if you try to sort something that's already sorted, is it any faster?*

Go's sort is based loosely on Engineering A Sort Function (1993) [PDF], which describes the rationale and techniques behind a good sorting routine. In particular, its performance when given certain types of input was carefully considered. Quicksort (the main algorithm used) has a worst-case run time of O(n²), and care has been taken to make sure this can't be abused.

Go prevents this by limiting the depth of the recursive calls to quicksort. Once it reaches its maximum depth it switches to Heapsort, which guarantees a worst-case run time of O(n log n).

## Tests

To keep the code simple and to allow the compiler to optimise as much as possible, I chose to sort various distributions of integers using`sort.Ints`

. I kept the length of the slices constant.
const size = 1e5

### Distributions

#### Ordered

What could be more simple than sorting a slice that's already sorted? Does having repeat elements help?`Ordered`

returns a slice of the requested length, with increasing, repeated elements. There should be `x`

distinct elements in the slice.
func Ordered(l, x int) []int { if x > l { x = l } s := make([]int, l) for i := range s { s[i] = i / (l / x) } return s }

#### Sawtooth

`Sawtooth`

and its reverse generate ordered sequences of length `x`

.
func Sawtooth(l, x int) []int { s := make([]int, l) for i := range s { s[i] = i % x } return s }

#### Organpipe

An increasing, then decreasing sequence of total length`x`

func Organpipe(l, x int) []int { s := make([]int, l) for i := range s { if i%x < x/2 { s[i] = i % x } else { s[i] = x - i%x - 1 } } return s }

#### Random

`Random`

generates a slice of integers picked from a pool of size `x`

. When x is 1, all elements are the same.
func Random(l, x int) []int { s := make([]int, l) for i := range s { s[i] = rand.Intn(x) } return s }

#### Distinct

A slight extension of`Random`

, `Distinct`

shuffles a slice of distinct integers, as if selecting from an infinite pool.
func Distinct(l, x int) []int { return rand.Perm(l) }

### Measurements

I measured the time taken (median of 51 runs) to sort slices of length 100,000. I also counted the number of calls to`Swap`

and `Less`

that were made, by embedding the slice in a struct and providing counters for those methods. Note that the methods have to be defined on the pointer receiver in order to modify the counters during sorting.
type profiledInts struct { lessCounter int swapCounter int sort.IntSlice } func (p *profiledInts) Less(i, j int) bool { p.lessCounter++ return p.IntSlice.Less(i, j) } func (p *profiledInts) Swap(i, j int) { p.swapCounter++ p.IntSlice.Swap(i, j) }

### x

The independent variable, or "horizontal axis" has a subtle interpretation that makes sense for all the distributions. As`x`

increases the input data contains more distinct values, the runs become longer, the repetitions less frequent. `x`

doesn't have any units, but at `x=1`

all the functions return a uniform slice with a single value, at the maximum value of `x`

, the values will almost all be distinct.
## Results

- Despite
`x`

affecting each distribution in a different way, the overall time taken for a particular value of`x`

looks quite similar. It consistently took 30 times as long to sort a slice of unique values than a slice of uniform values. - The number of comparisons (calls to
`Less`

) did not vary much between distributions. - Reversing the sawtooth distribution did very little to any metric.
- Sorting an already sorted slice is
*slightly*faster than other distributions, as it requires far fewer calls to`Swap`

. The time taken for a sorted slice could be 70% of a random slice, but would require less than 20% of the calls to`Swap`

, and 90% of the calls to`Less`

. - Ordered, Sawtooth, Reverse Sawtooth meet at the same point at large
`x`

as they all produce a sorted (reversed) slice. Organpipe takes slightly longer as it is a concatenation of a sorted and reversed slice. - The upwards trend reverses at high
`x`

as the required number of swaps drops dramatically. At low`x`

there are many elements with the same value that need to be brought together (requiring a swap). As`x`

gets higher there are fewer of each element, until at maximum`x`

all the distributions except random start off with a large section of elements in the correct position. Note that "in the correct position" is a stronger requirement than "sorted", as it requires the rest of the slice to not contain any elements that need to be inserted. - There is a blip at
`x=8`

.`Sort`

switches to insertion sort when the recursive calls come to sort a slice of length around 8, so it may be an interaction with that.

### Time

### Swap count

### Less count

## Conclusion

A useful rule of thumb to how Go's`Sort`

function will perform is to estimate the number of distinct values. The fewer, the faster. `Sort`

does not exhibit poor performance on a variety of common inputs, although how bad a malicious input could be has not *yet*been investigated. The design of

`Sort`

guarantees worst-case O(n log n) performance.