Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

sort: Stable merge is unstable if Less does not define a strict weak order #41951

Closed
alandonovan opened this issue Oct 13, 2020 · 5 comments
Closed

Comments

@alandonovan
Copy link
Contributor

@alandonovan alandonovan commented Oct 13, 2020

The block merge portion of sort.Stable does not appear to be stable when a sequence contains unordered pairs of values (e.g. NaN < x).

See https://play.golang.org/p/h_m2BDF5n63

	type F []float64
	func (p F) Less(i, j int) bool { return p[i] < p[j] } // note: IEEE-754 ordering, not sort.Float64s ordering

	// len=20: uses insertion sort
	a := F{4, 2, NaN, 3, 1, 4, 2, NaN, 3, 1, 4, 2, NaN, 3, 1, 4, 2, NaN, 3, 1}
	sort.Stable(a)
	fmt.Println(a, len(a)) // [2 4 NaN 1 2 3 4 NaN 1 2 3 4 NaN 1 2 3 4 NaN 1 3] 20
	
	// len=21: merges two insertion-sorted blocks
	b := F{4, 2, NaN, 3, 1, 4, 2, NaN, 3, 1, 4, 2, NaN, 3, 1, 4, 2, NaN, 3, 1, 0}
	sort.Stable(b)
	fmt.Println(b, len(b)) // [2 4 NaN 0 1 2 3 4 NaN 1 2 3 4 NaN 1 2 3 4 NaN 1 3] 21

Observe that the final 0 has migrated into the second NaN-bracketed portion.

Note that we are defining Less as float64 < float64 without the special handing that sort.Float64s does.

go version devel +5b509d993d Tue Oct 13 08:36:41 2020 +0000 linux/amd64

@alandonovan
Copy link
Contributor Author

@alandonovan alandonovan commented Oct 13, 2020

Perhaps the solution here is to document: "sort.Interface.Less must define a strict weak order, and float64 < float64 is not a strict weak order because it is not transitive (a < b and not c < b => a < c) for NaN values. Therefore do not use float64 < float64 for sorting."

C++ and Python's sort functions (std::stable_sort, sorted) are similarly unstable in the presence of NaN. Java's solution is to define a total order: java.lang.Double.compareTo is similar to Go's sort.Float64s but additionally orders -0.0 < 0.0.

@ALTree
Copy link
Member

@ALTree ALTree commented Oct 13, 2020

Related: #34915 (sort: document the ordering requirements of Less).

@dmitshur dmitshur changed the title sort.Stable merge is unstable sort: Stable merge is unstable Oct 13, 2020
@rsc
Copy link
Contributor

@rsc rsc commented Oct 13, 2020

As you figured out, the bug here is that Less isn't a less-than function.

@smasher164
Copy link
Member

@smasher164 smasher164 commented Oct 14, 2020

@alandonovan Is it okay to close this issue, since #34915 is resolved?

@alandonovan alandonovan changed the title sort: Stable merge is unstable sort: Stable merge is unstable if Less does not define a strict weak order Oct 14, 2020
@gopherbot
Copy link

@gopherbot gopherbot commented Oct 15, 2020

Change https://golang.org/cl/262657 mentions this issue: sort: update comments

gopherbot pushed a commit that referenced this issue Oct 16, 2020
- Describe requirements on Less more precisely.
- Standardize on x for the variable name of the data being sorted
  (was variously a, p, slice).
- Many other minor wording changes.

Fixes #41951.

Change-Id: Ic9e222a53ec035fcc3b5ddfc7f0eefbe1bb2890d
Reviewed-on: https://go-review.googlesource.com/c/go/+/262657
Trust: Russ Cox <rsc@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Rob Pike <r@golang.org>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
5 participants
You can’t perform that action at this time.