welcome at SebWalak.com

Sorting in Go

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

type Interface interface {
 Len() int
 Less(i, j int) bool
 Swap(i, j int)
}

Here’s an example:

type timedBoundary struct {
 time    time.Time
 //other fields
}

type timedBoundaries []timedBoundary

func (a timedBoundaries) Len() int           { return len(a) }
func (a timedBoundaries) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a timedBoundaries) Less(i, j int) bool { return a[i].time.Before(a[j].time) }

And then, using is as simple as:

var tbs []timedBoundary
...
sort.Sort(timedBoundaries(tbs))

As I am a fresh Gopher and also as I am coming with the baggage of Java background the suprising 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:

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

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.

Thumbnail