proposal: src/sort: Expand sort.Sort() and sort.Stable() to use generic types

[dshebib]

Proposal Details

This proposal is for expanding the sort package in the stdlib to use generics. The Sort and Slices packages have been updated to use generics to cover all other functions in the sort package, but calling Sort() on an arbitrary data structure still requires that the provided Interface implements Less(i, j int) bool and Swap(i, j int) instead of allowing for generics. This would be helpful for cases where the primary keys/values of an ordered data structure are not integers.

Example:

package main

import (
	"fmt"
	"slices"
	"sort"
)

//**want to use this interface**
type CustomDataInterface interface {
	Len() int
	Less(a, b string) bool
	Swap(a, b string)
}

type CustomData struct {
	Dat []string
}

func (cd *CustomData) Len() int {
	return len(cd.Dat)
}

func (cd *CustomData) Less(a, b string) bool {
	return a < b
}

func (cd *CustomData) Swap(a, b string) {
	idxA := slices.IndexFunc(cd.Dat, func(x string) bool { return x == a })
	idxB := slices.IndexFunc(cd.Dat, func(x string) bool { return x == b })
	cd.Dat[idxA] = b
	cd.Dat[idxB] = a
	return
}

func main() {
	letters := []string{"b", "a", "c", "d"}
	CD := &CustomData{Dat: letters}

	fmt.Printf("%v", CD.Dat)
	fmt.Println()

	//slices.Sort(CD.Dat) //works for slices
	sort.Sort(CD)
	fmt.Printf("%v", CD.Dat)
}

./prog.go:46:12: cannot use CD (variable of type *CustomData) as sort.Interface value in argument to sort.Sort: *CustomData does not implement sort.Interface (wrong type for method Less) have Less(string, string) bool want Less(int, int) bool

It looks like this wouldn't be too difficult to implement since the sort package already has some generated code for generics. I also didn't find other issues mentioning this proposal but may be missing something obvious.

[seankhliao]

It's unclear how the sort package would produce these keys of generic values to pass to the Less and Swap functions given it only knows Len (and therefore and index of 0 to (len-1)) of the structure to sort.

[randall77]

This is possible but it would require using new names in the sort package. We cannot change sort.Sort itself (and sort.Interface) at this point.

The Swap part of this proposal doesn't make any sense to me. First, your implementation is O(n), which is bad, and second I don't think it handles duplicate strings correctly.
I think Swap would have to be Swap(a,b *string), no? And at that point, why have Swap at all? If these new functions are generic on the element type, they can do the swap themselves without the interface. (Like slices.Sort does.) At that point, why not just use slices.SortFunc?

[gabyhelp]

Similar Issues

• slices: add Sort, SortStable, IsSorted, BinarySearch, and func variants #47619
• sort: make sorting easier, add Slice, SliceStable, SliceIsSorted, reflect.Swapper #16721
• sort: improve implementation #45422
• proposal: Go 2: Type parameterized interface default methods #33818

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[dshebib]

Right, this might have to be implemented as part of an iter package that uses the seq interface to access members. Because it would only be able to access members linearly it will be less efficient than slices.sort() but would accept more complex sturctures than just slices. As far as whether it is worth it to add this function (perhaps in the iter package itself or some other experimental package), it seems like that's part of a greater discussion in #61897 and elsewhere. The lack of other proposals suggests that most people are fine sticking to slices for most use cases.

func (it iter.Seq[*V comparable]) IterSort()
func (it iter.Seq2[*K comparable, *V any]) IterSort()

[randall77]

func (it iter.Seq[*V comparable]) IterSort()

I don't see how that signature works. Where is the result of the sort?

Given that under the hood it would have to use a slice anyway, I don't see the problem with:

s := slices.Collect(it)
slices.Sort(s)

And maybe it2 := slices.All(s) if you want to get back to an iterator afterwards.

[dshebib]

The sort would occur in-place using the pointer returned by the iterator. This would cause the actual data to be sorted, not just as a copy of a slice.

[randall77]

The sort would occur in-place using the pointer returned by the iterator. This would cause the actual data to be sorted, not just as a copy of a slice.

That's how C++ iterators work. That is not how Go iterators work.

[dshebib]

You caught me 😆 I guess my question is why not include that functionality if iterators which return by address are already being considered?

[randall77]

I don't think there are currently any proposals for return-by-address iterators.
Of course, you could make an iterator that returns pointers to entries in some data structure. But they wouldn't be seekable iterators like C++ has, so I'm not sure how useful that would be. For sort, something tells me it would be completely useless.