Custom sort fast sort slices by one or two criteria – Code Review

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

type point struct {
	x float64
	y int32
}

var points []point

I should now sort the slice based on its filed, based on user input x or from his fields y and then x,

I have read in many places that sort.Interface performs better than sort.SliceSo I’m doing the following for sorting by x:

type Slice struct {
	sort.Interface
	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...)
sort.Sort(S)

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...)
sort.Sort(S)

Here’s a complete example with some real data (someone might have noticed that the fragment xs is already sorted, but it’s just a dummy dataset, it never happens in my application).

Now I’m wondering if this is really the fastest way to sort, or if there’s a better way to do it.
any suggestion?


Leave a Comment