Update, Sep 15 2021: the current proposal is at #47619 (comment). - @rsc

This proposal is for use with #43651 (and also relies on the accompanying constraints package described in #45458). We propose adding a new generic function for sorting slices in the sort package and using this code to implement sort.Ints, sort.Float64s and sort.Strings much more efficiently. Similarly, we will do this for other functionality in the sort package.

If this proposal is accepted, the changes will be included with the first release of Go that implements #43651 (we currently expect that that will be Go 1.18).

Part 1 - exposing generic sort functions in the sort package API

We propose exposing a generic sort function for sorting a slice as part of the public API of the sort package. Specifically, a new exported function:

func SliceOf[T constraints.Ordered](x []T)

Typical invocation for some slice of an ordered type (like []int64) will look like this (type inference will obviate the need to specify a type):

    sort.SliceOf(s)

Sorts the provided slice in-place, similarly to today’s sort.Slice. The name of this function is subject to discussion.
With this function in the sort package, we can add deprecation notices to existing concrete sort functions: sort.Ints, sort.Float64s, sort.Strings - though these functions will remain in the package in line with Go 1 compatibility guarantee.

Part 2 - generic functions for additional sort package functionality

We propose to provide a generic version of the current sort.IsSorted function:

func SliceIsSortedOf[T constraints.Ordered](x []T)

Efficient stable sorts:

func SliceStableOf[T constraints.Ordered](x []T)

Binary search:

func SearchSliceOf[T constraints.Ordered](what T, x []T) int

Background - generic sort implementation

An internal sorting function:

func orderedSort[T constraints.Ordered](x []T)

Can be using the same implementation as the internal quickSort_func today, with the type parameter replacing the interface{} and having to provide a less function. Early benchmarks show that this approach is 3-4x faster than the current sort.Ints. This function can be added and used to implement exported functions like sort.Ints or sort.Strings even if we decide not to add new APIs via this proposal.