sort: document the ordering requirements of Less

[jowu]

What version of Go are you using (go version)?

$ go version
go version go1.13rc1 linux/amd64

But this should apply to all.

Does this issue reproduce with the latest release?

Yes.

sort doc should remind users that the 'less' function must be a total order.

[agnivade]

Hi @jowu - could you please explain what you mean by "total order" ? Thanks.

[jowu]

Sure. In short, the function has to meet these criteria: https://en.wikipedia.org/wiki/Total_order
Once you think about sorting, this is fairly obvious, but when you are working on something else, it's easy to forget (a colleague and I wasted a lot of time trying to find bugs elsewhere because we'd forgotten this basic property).

[randall77]

The less function does not need to be a total order. If it were, then there would be no difference between sort.Sort and sort.Stable. It is allowed that both Less(a,b) and Less(b,a) return false.

Less does need to be transitive.

[randall77]

I think the correct term is strict partial order.

[smasher164]

That being said, the incomparability of Less is transitive, where incomparability occurs when Less(a,b) and Less(b,a) return false.

So if Less(a,b) and Less(b,a) and Less(b,c) and Less(c,b) all return false, then Less(a,c) and Less(c,a) return false as well.

A specific term for this type of strict partial order is a strict weak ordering.

[randall77]

So if Less(a,b) and Less(b,a) and Less(b,c) and Less(c,b) all return false, then Less(a,c) and Less(c,a) return false as well.

I don't think that is right. You can have b be unordered with respect to both a and c and still have a<c.

[smasher164]

You can have b be unordered with respect to both a and c and still have a<c.

Doesn't that imply that there's no way to distinguish between two elements being equal and two elements being incomparable? Additionally, I don't think sort reorders the list [c, b, a] if b is unordered wrt a and c, but a<c.

[randall77]

Additionally, I don't think sort reorders the list [c, b, a] if b is unordered wrt a and c, but a<c.

Indeed, this is strange. I guess it is expected now that I think about it, quicksort won't work if a completely incomparable element is picked as the pivot. So maybe there is something stronger we require. Less must divide the input set into equivalence classes, where two elements are in the same equivalence class if !Less(a,b) && !Less(b,a), and the equivalence classes must be totally ordered? That certainly sounds like the strict weak ordering you mentioned.

package main

import "fmt"
import "sort"

type S string

func f(a []S) {
	sort.Slice(a, func(i, j int) bool {
		if a[i] == "a" && a[j] == "c" {
			return true
		}
		return false
	})
	fmt.Printf("%v\n", a)
}

func main() {
	f([]S{"c", "b", "a"})
	f([]S{"c", "a", "b"})
}

prints

[c b a]
[a c b]

[ianlancetaylor]

@smasher164

Doesn't that imply that there's no way to distinguish between two elements being equal and two elements being incomparable?

What does it mean to sort a list of values when some of the values are incomparable? What do you expect to happen?

[smasher164]

@randall77

Less must divide the input set into equivalence classes, where two elements are in the same equivalence class if !Less(a,b) && !Less(b,a), and the equivalence classes must be totally ordered?

Yes, that is exactly the equivalence relation we want. We want a totally-ordered partition where Less(a,b) implies either Less(a,c) OR Less(c,b).

@ianlancetaylor

What does it mean to sort a list of values when some of the values are incomparable? What do you expect to happen?

If incomparability is transitive, then I should expect incomparable values to be grouped together. However, if that contract is violated like in Keith's example, then the sort may not be accurate.

[gopherbot]

Change https://golang.org/cl/261959 mentions this issue: sort: document requirements of Less relation