Go Proposal: first-class support for sorting slices

Datetime:2016-08-23 05:14:58          Topic: Golang           Share

I propose we make sorting slices a first class concept in Go 1.8.

I think everybody appreciates the cute sort.Interface type at this point, but the reality is that:

  • nobody really sorts anything except slices (the handful of exceptions can keep doing what they're doing)
  • the Len and Swap functions are redundant. They're always the same for slices.
  • naming a new type (e.g. "widgetsByName") is tedious to many (including me; I still loathe it after 6+ years)
  • making a new type and three methods at the top-level (because it has to have methods, so it can't be a local type) is more difficult to read, since I'd prefer my Less function inline with my code, in context.

I think we should add to package sort at least:

package sort

// Slice sorts the provided slice using the function less.
// The sort is not stable.
// If slice is not a slice, Slice panics.
func Slice(slice interface{}, less func(i, j int) bool)

And maybe at the same time, or in the future:

// SliceSorter returns an sorter for the provided slice, suitable
// for with Reverse or Stable.
// If slice is not a slice, SliceSorter panics.
func SliceSorter(slice interface{}, less func(i, j int) bool) Interface

The assumption is that the user's less function would close over the data to be sorted.

For speed, this would not be purely reflect-based (except for one call to to get the slice length). The implementation would generate a custom swapper as needed for the type of the slice elements such that it's compatible with the GC & write barriers. I did a prototype of this which shows that it's as fast as the typical way.

I think there's plenty of evidence in the Github BigQuery dataset that we're making sort way too hard to users.

/cc@griesemer @robpike @ianlancetaylor @adg @broady





About List