Open
Description
The doc for sort.Slice states:
// The less function must satisfy the same requirements as
// the Interface type's Less method.This is referring to the less function interface here:
// Less must describe a transitive ordering:
// - if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well.
// - if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well.This describes only transitive ordering. In contrast, the underlying algorithm, pdqsort, requires strict weak ordering.
This is an important distinction. If a comparator is, for example:
- reflexive
- transitive
Then it will be conforming to the documented requirements yet will still cause crashes under nebulous implementation defined circumstances. e.g. the number of elements to sort is greater than 33, and elements happen to be in a specific order.
To fix:
Change the documented requirement of sort.Slice to what is stated in sort.SortFunc.
// SortFunc sorts the slice x in ascending order as determined by the cmp
// function. This sort is not guaranteed to be stable.
// cmp(a, b) should return a negative number when a < b, a positive number when
// a > b and zero when a == b or a and b are incomparable in the sense of
// a strict weak ordering.
//
// SortFunc requires that cmp is a strict weak ordering.
// See https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings.
// The function should return 0 for incomparable items.