sort

Find function #

Find uses binary search to find and return the smallest index i in [0, n) at which cmp(i) <= 0. If there is no such index i, Find returns i = n. The found result is true if i < n and cmp(i) == 0. Find calls cmp(i) only for i in the range [0, n). To permit binary search, Find requires that cmp(i) > 0 for a leading prefix of the range, cmp(i) == 0 in the middle, and cmp(i) < 0 for the final suffix of the range. (Each subrange could be empty.) The usual way to establish this condition is to interpret cmp(i) as a comparison of a desired target value t against entry i in an underlying indexed data structure x, returning <0, 0, and >0 when t < x[i], t == x[i], and t > x[i], respectively. For example, to look for a particular string in a sorted, random-access list of strings: i, found := sort.Find(x.Len(), func(i int) int { return strings.Compare(target, x.At(i)) }) if found { fmt.Printf("found %s at entry %d\n", target, i) } else { fmt.Printf("%s not found, would insert at %d", target, i) }

func Find(n int, cmp func(int) int) (i int, found bool)

Float64s function #

Float64s sorts a slice of float64s in increasing order. Not-a-number (NaN) values are ordered before other values. Note: as of Go 1.22, this function simply calls [slices.Sort].

func Float64s(x []float64)

Float64sAreSorted function #

Float64sAreSorted reports whether the slice x is sorted in increasing order, with not-a-number (NaN) values before any other values. Note: as of Go 1.22, this function simply calls [slices.IsSorted].

func Float64sAreSorted(x []float64) bool

Ints function #

Ints sorts a slice of ints in increasing order. Note: as of Go 1.22, this function simply calls [slices.Sort].

func Ints(x []int)

IntsAreSorted function #

IntsAreSorted reports whether the slice x is sorted in increasing order. Note: as of Go 1.22, this function simply calls [slices.IsSorted].

func IntsAreSorted(x []int) bool

IsSorted function #

IsSorted reports whether data is sorted. Note: in many situations, the newer [slices.IsSortedFunc] function is more ergonomic and runs faster.

func IsSorted(data Interface) bool

Len method #

func (x IntSlice) Len() int

Len method #

func (x StringSlice) Len() int

Len method #

func (x Float64Slice) Len() int

Less method #

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 int, j int) bool

Less method #

func (x IntSlice) Less(i int, j int) bool

Less method #

func (x StringSlice) Less(i int, j int) bool

Less method #

Less returns the opposite of the embedded implementation's Less method.

func (r reverse) Less(i int, j int) bool

Next method #

func (r *xorshift) Next() uint64

Reverse function #

Reverse returns the reverse order for data.

func Reverse(data Interface) Interface

Search method #

Search returns the result of applying [SearchFloat64s] to the receiver and x.

func (p Float64Slice) Search(x float64) int

Search method #

Search returns the result of applying [SearchInts] to the receiver and x.

func (p IntSlice) Search(x int) int

Search function #

Search uses binary search to find and return the smallest index i in [0, n) at which f(i) is true, assuming that on the range [0, n), f(i) == true implies f(i+1) == true. That is, Search requires that f is false for some (possibly empty) prefix of the input range [0, n) and then true for the (possibly empty) remainder; Search returns the first true index. If there is no such index, Search returns n. (Note that the "not found" return value is not -1 as in, for instance, strings.Index.) Search calls f(i) only for i in the range [0, n). A common use of Search is to find the index i for a value x in a sorted, indexable data structure such as an array or slice. In this case, the argument f, typically a closure, captures the value to be searched for, and how the data structure is indexed and ordered. For instance, given a slice data sorted in ascending order, the call Search(len(data), func(i int) bool { return data[i] >= 23 }) returns the smallest index i such that data[i] >= 23. If the caller wants to find whether 23 is in the slice, it must test data[i] == 23 separately. Searching data sorted in descending order would use the <= operator instead of the >= operator. To complete the example above, the following code tries to find the value x in an integer slice data sorted in ascending order: x := 23 i := sort.Search(len(data), func(i int) bool { return data[i] >= x }) if i < len(data) && data[i] == x { // x is present at data[i] } else { // x is not present in data, // but i is the index where it would be inserted. } As a more whimsical example, this program guesses your number: func GuessingGame() { var s string fmt.Printf("Pick an integer from 0 to 100.\n") answer := sort.Search(100, func(i int) bool { fmt.Printf("Is your number <= %d? ", i) fmt.Scanf("%s", &s) return s != "" && s[0] == 'y' }) fmt.Printf("Your number is %d.\n", answer) }

func Search(n int, f func(int) bool) int

Search method #

Search returns the result of applying [SearchStrings] to the receiver and x.

func (p StringSlice) Search(x string) int

SearchFloat64s function #

SearchFloat64s searches for x in a sorted slice of float64s and returns the index as specified by [Search]. The return value is the index to insert x if x is not present (it could be len(a)). The slice must be sorted in ascending order.

func SearchFloat64s(a []float64, x float64) int

SearchInts function #

SearchInts searches for x in a sorted slice of ints and returns the index as specified by [Search]. The return value is the index to insert x if x is not present (it could be len(a)). The slice must be sorted in ascending order.

func SearchInts(a []int, x int) int

SearchStrings function #

SearchStrings searches for x in a sorted slice of strings and returns the index as specified by Search. The return value is the index to insert x if x is not present (it could be len(a)). The slice must be sorted in ascending order.

func SearchStrings(a []string, x string) int

Slice function #

Slice sorts the slice x given the provided less function. It panics if x is not a slice. The sort is not guaranteed to be stable: equal elements may be reversed from their original order. For a stable sort, use [SliceStable]. The less function must satisfy the same requirements as the Interface type's Less method. Note: in many situations, the newer [slices.SortFunc] function is more ergonomic and runs faster.

func Slice(x any, less func(i int, j int) bool)

SliceIsSorted function #

SliceIsSorted reports whether the slice x is sorted according to the provided less function. It panics if x is not a slice. Note: in many situations, the newer [slices.IsSortedFunc] function is more ergonomic and runs faster.

func SliceIsSorted(x any, less func(i int, j int) bool) bool

SliceStable function #

SliceStable sorts the slice x using the provided less function, keeping equal elements in their original order. It panics if x is not a slice. The less function must satisfy the same requirements as the Interface type's Less method. Note: in many situations, the newer [slices.SortStableFunc] function is more ergonomic and runs faster.

func SliceStable(x any, less func(i int, j int) bool)

Sort function #

Sort sorts data in ascending order as determined by the Less method. 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. Note: in many situations, the newer [slices.SortFunc] function is more ergonomic and runs faster.

func Sort(data Interface)

Sort method #

Sort is a convenience method: x.Sort() calls Sort(x).

func (x IntSlice) Sort()

Sort method #

Sort is a convenience method: x.Sort() calls Sort(x).

func (x Float64Slice) Sort()

Sort method #

Sort is a convenience method: x.Sort() calls Sort(x).

func (x StringSlice) Sort()

Stable function #

Stable sorts data in ascending order as determined by the Less method, while keeping the original order of equal elements. It makes one call to data.Len to determine n, O(n*log(n)) calls to data.Less and O(n*log(n)*log(n)) calls to data.Swap. Note: in many situations, the newer slices.SortStableFunc function is more ergonomic and runs faster.

func Stable(data Interface)

Strings function #

Strings sorts a slice of strings in increasing order. Note: as of Go 1.22, this function simply calls [slices.Sort].

func Strings(x []string)

StringsAreSorted function #

StringsAreSorted reports whether the slice x is sorted in increasing order. Note: as of Go 1.22, this function simply calls [slices.IsSorted].

func StringsAreSorted(x []string) bool

Swap method #

func (x IntSlice) Swap(i int, j int)

Swap method #

func (x StringSlice) Swap(i int, j int)

Swap method #

func (x Float64Slice) Swap(i int, j int)

breakPatterns function #

breakPatterns scatters some elements around in an attempt to break some patterns that might cause imbalanced partitions in quicksort.

func breakPatterns(data Interface, a int, b int)

breakPatterns_func function #

breakPatterns_func scatters some elements around in an attempt to break some patterns that might cause imbalanced partitions in quicksort.

func breakPatterns_func(data lessSwap, a int, b int)

choosePivot function #

choosePivot chooses a pivot in data[a:b]. [0,8): chooses a static pivot. [8,shortestNinther): uses the simple median-of-three method. [shortestNinther,∞): uses the Tukey ninther method.

func choosePivot(data Interface, a int, b int) (pivot int, hint sortedHint)

choosePivot_func function #

choosePivot_func chooses a pivot in data[a:b]. [0,8): chooses a static pivot. [8,shortestNinther): uses the simple median-of-three method. [shortestNinther,∞): uses the Tukey ninther method.

func choosePivot_func(data lessSwap, a int, b int) (pivot int, hint sortedHint)

heapSort function #

func heapSort(data Interface, a int, b int)

heapSort_func function #

func heapSort_func(data lessSwap, a int, b int)

insertionSort function #

insertionSort sorts data[a:b] using insertion sort.

func insertionSort(data Interface, a int, b int)

insertionSort_func function #

insertionSort_func sorts data[a:b] using insertion sort.

func insertionSort_func(data lessSwap, a int, b int)

isNaN function #

isNaN is a copy of math.IsNaN to avoid a dependency on the math package.

func isNaN(f float64) bool

median function #

median returns x where data[x] is the median of data[a],data[b],data[c], where x is a, b, or c.

func median(data Interface, a int, b int, c int, swaps *int) int

medianAdjacent function #

medianAdjacent finds the median of data[a - 1], data[a], data[a + 1] and stores the index into a.

func medianAdjacent(data Interface, a int, swaps *int) int

medianAdjacent_func function #

medianAdjacent_func finds the median of data[a - 1], data[a], data[a + 1] and stores the index into a.

func medianAdjacent_func(data lessSwap, a int, swaps *int) int

median_func function #

median_func returns x where data[x] is the median of data[a],data[b],data[c], where x is a, b, or c.

func median_func(data lessSwap, a int, b int, c int, swaps *int) int

nextPowerOfTwo function #

func nextPowerOfTwo(length int) uint

order2 function #

order2 returns x,y where data[x] <= data[y], where x,y=a,b or x,y=b,a.

func order2(data Interface, a int, b int, swaps *int) (int, int)

order2_func function #

order2_func returns x,y where data[x] <= data[y], where x,y=a,b or x,y=b,a.

func order2_func(data lessSwap, a int, b int, swaps *int) (int, int)

partialInsertionSort function #

partialInsertionSort partially sorts a slice, returns true if the slice is sorted at the end.

func partialInsertionSort(data Interface, a int, b int) bool

partialInsertionSort_func function #

partialInsertionSort_func partially sorts a slice, returns true if the slice is sorted at the end.

func partialInsertionSort_func(data lessSwap, a int, b int) bool

partition function #

partition does one quicksort partition. Let p = data[pivot] Moves elements in data[a:b] around, so that data[i]

=p for inewpivot. On return, data[newpivot] = p

func partition(data Interface, a int, b int, pivot int) (newpivot int, alreadyPartitioned bool)

partitionEqual function #

partitionEqual partitions data[a:b] into elements equal to data[pivot] followed by elements greater than data[pivot]. It assumed that data[a:b] does not contain elements smaller than the data[pivot].

func partitionEqual(data Interface, a int, b int, pivot int) (newpivot int)

partitionEqual_func function #

partitionEqual_func partitions data[a:b] into elements equal to data[pivot] followed by elements greater than data[pivot]. It assumed that data[a:b] does not contain elements smaller than the data[pivot].

func partitionEqual_func(data lessSwap, a int, b int, pivot int) (newpivot int)

partition_func function #

partition_func does one quicksort partition. Let p = data[pivot] Moves elements in data[a:b] around, so that data[i]

=p for inewpivot. On return, data[newpivot] = p

func partition_func(data lessSwap, a int, b int, pivot int) (newpivot int, alreadyPartitioned bool)

pdqsort function #

pdqsort sorts data[a:b]. The algorithm based on pattern-defeating quicksort(pdqsort), but without the optimizations from BlockQuicksort. pdqsort paper: https://arxiv.org/pdf/2106.05123.pdf C++ implementation: https://github.com/orlp/pdqsort Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/ limit is the number of allowed bad (very unbalanced) pivots before falling back to heapsort.

func pdqsort(data Interface, a int, b int, limit int)

pdqsort_func function #

pdqsort_func sorts data[a:b]. The algorithm based on pattern-defeating quicksort(pdqsort), but without the optimizations from BlockQuicksort. pdqsort paper: https://arxiv.org/pdf/2106.05123.pdf C++ implementation: https://github.com/orlp/pdqsort Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/ limit is the number of allowed bad (very unbalanced) pivots before falling back to heapsort.

func pdqsort_func(data lessSwap, a int, b int, limit int)

reverseRange function #

func reverseRange(data Interface, a int, b int)

reverseRange_func function #

func reverseRange_func(data lessSwap, a int, b int)

rotate function #

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, and it assumes non-degenerate arguments: a < m && m < b.

func rotate(data Interface, a int, m int, b int)

rotate_func function #

rotate_func 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, and it assumes non-degenerate arguments: a < m && m < b.

func rotate_func(data lessSwap, a int, m int, b int)

siftDown function #

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 int, hi int, first int)

siftDown_func function #

siftDown_func implements the heap property on data[lo:hi]. first is an offset into the array where the root of the heap lies.

func siftDown_func(data lessSwap, lo int, hi int, first int)

stable function #

func stable(data Interface, n int)

stable_func function #

func stable_func(data lessSwap, n int)

swapRange function #

func swapRange(data Interface, a int, b int, n int)

swapRange_func function #

func swapRange_func(data lessSwap, a int, b int, n int)

symMerge function #

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 Computer Science, pages 714-723. Springer, 2004. Let M = m-a and N = b-n. Wolog M < N. The recursion depth is bound by ceil(log(N+M)). The algorithm needs O(M*log(N/M + 1)) calls to data.Less. The algorithm needs O((M+N)*log(M)) calls to data.Swap. The paper gives O((M+N)*log(M)) as the number of assignments assuming a rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation in the paper carries through for Swap operations, especially as the block swapping rotate uses only O(M+N) Swaps. symMerge assumes non-degenerate arguments: a < m && m < b. Having the caller check this condition eliminates many leaf recursion calls, which improves performance.

func symMerge(data Interface, a int, m int, b int)

symMerge_func function #

symMerge_func 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 Computer Science, pages 714-723. Springer, 2004. Let M = m-a and N = b-n. Wolog M < N. The recursion depth is bound by ceil(log(N+M)). The algorithm needs O(M*log(N/M + 1)) calls to data.Less. The algorithm needs O((M+N)*log(M)) calls to data.Swap. The paper gives O((M+N)*log(M)) as the number of assignments assuming a rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation in the paper carries through for Swap operations, especially as the block swapping rotate uses only O(M+N) Swaps. symMerge assumes non-degenerate arguments: a < m && m < b. Having the caller check this condition eliminates many leaf recursion calls, which improves performance.

func symMerge_func(data lessSwap, a int, m int, b int)