Fast sort slice of custom type by one or two criteria

I need to sort a slice of custom type as fast as possible.
The generalize the problem, I have a slice points defined as:

type point struct {
	x float64
	y int32

var points []point

I need now, based on the user input, sort the slice either by its filed x or by its fields y and then x.

I have read in multiple places that sort.Interface performs better than sort.Slice, so I am doing as follow for sorting by x:

type Slice struct {
	idx []int

func (s Slice) Swap(i, j int) {
	s.Interface.Swap(i, j)
	s.idx[i], s.idx[j] = s.idx[j], s.idx[i]

func NewSlice(n sort.Interface) *Slice {
	s := &Slice{Interface: n, idx: make([]int, n.Len())}
	for i := range s.idx {
		s.idx[i] = i
	return s

func NewFloat64Slice(n ...float64) *Slice {
	return NewSlice(sort.Float64Slice(n))

/// in main
var S *Slice

xx := make([]float64, len(points))
for v := range points {
	xx[v] = points[v].x
S = NewFloat64Slice(xx...)

sortedbyX := make([]point, len(points))
for j, i := range S.idx {
	sortedbyX[j] = points[i]

or for sorting by y and then x:

type byYX []point

func (pnts byYX) Len() int      { return len(pnts) }
func (pnts byYX) Swap(i, j int) { pnts[i], pnts[j] = pnts[j], pnts[i] }
func (pnts byYX) Less(i, j int) bool {
	if pnts[i].y == pnts[j].y {
		return pnts[i].x < pnts[j].x
	} else {
		return pnts[i].y < pnts[j].y

func NewCSlice(n ...point) *Slice {
	return NewSlice(byYX(n))

/// in main
S = NewCSlice(points...)

Here is a full examples with some real data (someone might noticed that the slice xs is already sorted, but it is just a dummy dataset here, this never happens in my application).

I am now wondering whether this is indeed the fastest way to sort, or if there is a better way to do it.
Any suggestion?

Hi Pisistrato,
If you would like to do this according to the performance you should probably implement your own solution of knows algorithms. The choice of algorithm should depends on your dataset.

and probably more.

You can choose proper algorithm based on number of elements that you will have to sort.
For example QuickSort complexity could be O(n*log n) what means that it would be better for big volume and it is probably used in go. Bubble sort complexity is O(n^2) and should be never used :slight_smile:

Hi Przemo, I am sorry if I was not clear. I am rather interested in knowing if my code was idiomatic or not, whether what I coded could have been done better/faster/more efficient, regardless of the underlying sorting algorithm :slight_smile:

Off topic, I read that since Go 1.9 quicksort has been replaced by pdqsort. Also read somewhere that there is an even faster algorithm out there, but cannot recall the nameā€¦