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

Jump to bottom

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

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

alandonovan opened this issue Oct 13, 2020 · 5 comments
Labels
FrozenDueToAge

Comments

@alandonovan
Copy link
Contributor

alandonovan commented Oct 13, 2020 •
edited

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 commented Oct 13, 2020 •
edited

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 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 commented Oct 13, 2020

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

@smasher164
Copy link
Member

@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

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

gopherbot pushed a commit that referenced this issue Oct 16, 2020
@rsc
sort: update comments
af87480 
- 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>
@golang golang locked and limited conversation to collaborators Oct 15, 2021
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
5 participants
@rsc @ALTree @alandonovan @gopherbot @smasher164