1 files changed, 64 insertions, 43 deletions

diff --git a/src/sort/sort.go b/src/sort/sort.go
index dd5bb3762e..cbaa8c3aac 100644
--- a/src/sort/sort.go
+++ b/src/sort/sort.go
@@ -4,24 +4,37 @@
 
 //go:generate go run genzfunc.go
 
-// Package sort provides primitives for sorting slices and user-defined
-// collections.
+// Package sort provides primitives for sorting slices and user-defined collections.
 package sort
 
-// A type, typically a collection, that satisfies sort.Interface can be
-// sorted by the routines in this package. The methods require that the
-// elements of the collection be enumerated by an integer index.
+// An implementation of Interface can be sorted by the routines in this package.
+// The methods refer to elements of the underlying collection by integer index.
 type Interface interface {
 	// Len is the number of elements in the collection.
 	Len() int
-	// Less reports whether the element with
-	// index i should sort before the element with index j.
+
+	// Less reports whether the element with index i
+	// must sort before the element with index j.
+	//
+	// If both Less(i, j) and Less(j, i) are false,
+	// then the elements at index i and j are considered equal.
+	// Sort may place equal elements in any order in the final result,
+	// while Stable preserves the original input order of equal elements.
+	//
+	// 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.
+	//
+	// Note that floating-point comparison (the < operator on float32 or float64 values)
+	// is not a transitive ordering when not-a-number (NaN) values are involved.
+	// See Float64Slice.Less for a correct implementation for floating-point values.
 	Less(i, j int) bool
+
 	// Swap swaps the elements with indexes i and j.
 	Swap(i, j int)
 }
 
-// Insertion sort
+// insertionSort sorts data[a:b] using insertion sort.
 func insertionSort(data Interface, a, b int) {
 	for i := a + 1; i < b; i++ {
 		for j := i; j > a && data.Less(j, j-1); j-- {
@@ -30,7 +43,7 @@ func insertionSort(data Interface, a, b int) {
 	}
 }
 
-// siftDown implements the heap property on data[lo, hi).
+// siftDown implements the heap property on data[lo:hi].
 // first is an offset into the array where the root of the heap lies.
 func siftDown(data Interface, lo, hi, first int) {
 	root := lo
@@ -211,7 +224,7 @@ func quickSort(data Interface, a, b, maxDepth int) {
 }
 
 // Sort sorts data.
-// It makes one call to data.Len to determine n, and O(n*log(n)) calls to
+// It makes one call to data.Len to determine n and O(n*log(n)) calls to
 // data.Less and data.Swap. The sort is not guaranteed to be stable.
 func Sort(data Interface) {
 	n := data.Len()
@@ -268,60 +281,68 @@ func IsSorted(data Interface) bool {
 // IntSlice attaches the methods of Interface to []int, sorting in increasing order.
 type IntSlice []int
 
-func (p IntSlice) Len() int           { return len(p) }
-func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
-func (p IntSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
+func (x IntSlice) Len() int           { return len(x) }
+func (x IntSlice) Less(i, j int) bool { return x[i] < x[j] }
+func (x IntSlice) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }
 
-// Sort is a convenience method.
-func (p IntSlice) Sort() { Sort(p) }
+// Sort is a convenience method: x.Sort() calls Sort(x).
+func (x IntSlice) Sort() { Sort(x) }
 
-// Float64Slice attaches the methods of Interface to []float64, sorting in increasing order
-// (not-a-number values are treated as less than other values).
+// Float64Slice implements Interface for a []float64, sorting in increasing order,
+// with not-a-number (NaN) values ordered before other values.
 type Float64Slice []float64
 
-func (p Float64Slice) Len() int           { return len(p) }
-func (p Float64Slice) Less(i, j int) bool { return p[i] < p[j] || isNaN(p[i]) && !isNaN(p[j]) }
-func (p Float64Slice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
+func (x Float64Slice) Len() int { return len(x) }
+
+// Less reports whether x[i] should be ordered before x[j], as required by the sort Interface.
+// Note that floating-point comparison by itself is not a transitive relation: it does not
+// report a consistent ordering for not-a-number (NaN) values.
+// This implementation of Less places NaN values before any others, by using:
+//
+//	x[i] < x[j] || (math.IsNaN(x[i]) && !math.IsNaN(x[j]))
+//
+func (x Float64Slice) Less(i, j int) bool { return x[i] < x[j] || (isNaN(x[i]) && !isNaN(x[j])) }
+func (x Float64Slice) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }
 
 // isNaN is a copy of math.IsNaN to avoid a dependency on the math package.
 func isNaN(f float64) bool {
 	return f != f
 }
 
-// Sort is a convenience method.
-func (p Float64Slice) Sort() { Sort(p) }
+// Sort is a convenience method: x.Sort() calls Sort(x).
+func (x Float64Slice) Sort() { Sort(x) }
 
 // StringSlice attaches the methods of Interface to []string, sorting in increasing order.
 type StringSlice []string
 
-func (p StringSlice) Len() int           { return len(p) }
-func (p StringSlice) Less(i, j int) bool { return p[i] < p[j] }
-func (p StringSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
+func (x StringSlice) Len() int           { return len(x) }
+func (x StringSlice) Less(i, j int) bool { return x[i] < x[j] }
+func (x StringSlice) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }
 
-// Sort is a convenience method.
-func (p StringSlice) Sort() { Sort(p) }
+// Sort is a convenience method: x.Sort() calls Sort(x).
+func (x StringSlice) Sort() { Sort(x) }
 
 // Convenience wrappers for common cases
 
 // Ints sorts a slice of ints in increasing order.
-func Ints(a []int) { Sort(IntSlice(a)) }
+func Ints(x []int) { Sort(IntSlice(x)) }
 
-// Float64s sorts a slice of float64s in increasing order
-// (not-a-number values are treated as less than other values).
-func Float64s(a []float64) { Sort(Float64Slice(a)) }
+// Float64s sorts a slice of float64s in increasing order.
+// Not-a-number (NaN) values are ordered before other values.
+func Float64s(x []float64) { Sort(Float64Slice(x)) }
 
 // Strings sorts a slice of strings in increasing order.
-func Strings(a []string) { Sort(StringSlice(a)) }
+func Strings(x []string) { Sort(StringSlice(x)) }
 
-// IntsAreSorted tests whether a slice of ints is sorted in increasing order.
-func IntsAreSorted(a []int) bool { return IsSorted(IntSlice(a)) }
+// IntsAreSorted reports whether the slice x is sorted in increasing order.
+func IntsAreSorted(x []int) bool { return IsSorted(IntSlice(x)) }
 
-// Float64sAreSorted tests whether a slice of float64s is sorted in increasing order
-// (not-a-number values are treated as less than other values).
-func Float64sAreSorted(a []float64) bool { return IsSorted(Float64Slice(a)) }
+// Float64sAreSorted reports whether the slice x is sorted in increasing order,
+// with not-a-number (NaN) values before any other values.
+func Float64sAreSorted(x []float64) bool { return IsSorted(Float64Slice(x)) }
 
-// StringsAreSorted tests whether a slice of strings is sorted in increasing order.
-func StringsAreSorted(a []string) bool { return IsSorted(StringSlice(a)) }
+// StringsAreSorted reports whether the slice x is sorted in increasing order.
+func StringsAreSorted(x []string) bool { return IsSorted(StringSlice(x)) }
 
 // Notes on stable sorting:
 // The used algorithms are simple and provable correct on all input and use
@@ -381,7 +402,7 @@ func stable(data Interface, n int) {
 	}
 }
 
-// SymMerge merges the two sorted subsequences data[a:m] and data[m:b] using
+// symMerge merges the two sorted subsequences data[a:m] and data[m:b] using
 // the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum
 // Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz
 // Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in
@@ -482,10 +503,10 @@ func symMerge(data Interface, a, m, b int) {
 	}
 }
 
-// Rotate two consecutive blocks u = data[a:m] and v = data[m:b] in data:
+// rotate rotates two consecutive blocks u = data[a:m] and v = data[m:b] in data:
 // Data of the form 'x u v y' is changed to 'x v u y'.
-// Rotate performs at most b-a many calls to data.Swap.
-// Rotate assumes non-degenerate arguments: a < m && m < b.
+// rotate performs at most b-a many calls to data.Swap,
+// and it assumes non-degenerate arguments: a < m && m < b.
 func rotate(data Interface, a, m, b int) {
 	i := m - a
 	j := b - m