Sorting in Go

Sorting can be easily implemented by using Go's interface sort.Interface declared as

1type Interface interface {
2 Len() int
3 Less(i, j int) bool
4 Swap(i, j int)
5}

Here's an example:

 1type timedBoundary struct {
 2 time    time.Time
 3 //other fields
 4}
 5
 6type timedBoundaries []timedBoundary
 7
 8func (a timedBoundaries) Len() int           { return len(a) }
 9func (a timedBoundaries) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
10func (a timedBoundaries) Less(i, j int) bool { return a[i].time.Before(a[j].time) }

And then, using is as simple as:

1var tbs []timedBoundary
2...
3sort.Sort(timedBoundaries(tbs))

As I am a fresh Gopher and also as I am coming with the baggage of Java background the surprising aspects for me were:

  • this interface is to be implemented on a collection rather than on a structure held within (timedBoundary)
  • the method receiver has to be a named type not a slice of named types, hence introduction of timedBoundaries type
  • the sort.Sort() function is not guaranteed to be stable which means the non-primitive types having same sorting key can migrate around in your slice

There is another sorting utility to use if lack of stability is an issue for you, here is the signature

func SliceStable(slice interface{}, less func(i, j int) bool)

Using it is slightly different:

1sort.SliceStable(tbs, func(i, j int) bool {
2 return tbs[i].time.Before(tbs[j].time)
3})

You will also avoid creating the named type.

The sort.SliceStable function is stable but quick performance test revealed it is taking about 1.5 time of sort.Sort.