Black Lives Matter. Support the Equal Justice Initiative.

# Package sort

`import "sort"`
Overview
Index
Examples

## Overview ▾

Package sort provides primitives for sorting slices and user-defined collections.

Example

```[Bob: 31 John: 42 Michael: 17 Jenny: 26]
[Michael: 17 Jenny: 26 Bob: 31 John: 42]
[John: 42 Bob: 31 Jenny: 26 Michael: 17]
```

Example (SortKeys)

ExampleSortKeys demonstrates a technique for sorting a struct type using programmable sort criteria.

```By name: [{Earth 1 1} {Mars 0.107 1.5} {Mercury 0.055 0.4} {Venus 0.815 0.7}]
By mass: [{Mercury 0.055 0.4} {Mars 0.107 1.5} {Venus 0.815 0.7} {Earth 1 1}]
By distance: [{Mercury 0.055 0.4} {Venus 0.815 0.7} {Earth 1 1} {Mars 0.107 1.5}]
By decreasing distance: [{Mars 0.107 1.5} {Earth 1 1} {Venus 0.815 0.7} {Mercury 0.055 0.4}]
```

Example (SortMultiKeys)

ExampleMultiKeys demonstrates a technique for sorting a struct type using different sets of multiple fields in the comparison. We chain together "Less" functions, each of which compares a single field.

```By user: [{dmr C 100} {glenda Go 200} {gri Go 100} {gri Smalltalk 80} {ken C 150} {ken Go 200} {r Go 100} {r C 150} {rsc Go 200}]
By user,<lines: [{dmr C 100} {glenda Go 200} {gri Smalltalk 80} {gri Go 100} {ken C 150} {ken Go 200} {r Go 100} {r C 150} {rsc Go 200}]
By user,>lines: [{dmr C 100} {glenda Go 200} {gri Go 100} {gri Smalltalk 80} {ken Go 200} {ken C 150} {r C 150} {r Go 100} {rsc Go 200}]
By language,<lines: [{dmr C 100} {ken C 150} {r C 150} {r Go 100} {gri Go 100} {ken Go 200} {glenda Go 200} {rsc Go 200} {gri Smalltalk 80}]
By language,<lines,user: [{dmr C 100} {ken C 150} {r C 150} {gri Go 100} {r Go 100} {glenda Go 200} {ken Go 200} {rsc Go 200} {gri Smalltalk 80}]
```

Example (SortWrapper)

```Organs by weight:
prostate (62g)
pancreas (131g)
spleen   (162g)
heart    (290g)
brain    (1340g)
liver    (1494g)
Organs by name:
brain    (1340g)
heart    (290g)
liver    (1494g)
pancreas (131g)
prostate (62g)
spleen   (162g)
```

## func Float64s¶

`func Float64s(x []float64)`

Float64s sorts a slice of float64s in increasing order. Not-a-number (NaN) values are ordered before other values.

Example

```[-3.8 -1.3 0.7 2.6 5.2]
[NaN -Inf 0 +Inf]
```

## func Float64sAreSorted¶

`func Float64sAreSorted(x []float64) bool`

Float64sAreSorted reports whether the slice x is sorted in increasing order, with not-a-number (NaN) values before any other values.

Example

```true
false
false
```

## func Ints¶

`func Ints(x []int)`

Ints sorts a slice of ints in increasing order.

Example

```[1 2 3 4 5 6]
```

## func IntsAreSorted¶

`func IntsAreSorted(x []int) bool`

IntsAreSorted reports whether the slice x is sorted in increasing order.

Example

```true
false
false
```

## func IsSorted¶

`func IsSorted(data Interface) bool`

IsSorted reports whether data is sorted.

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

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'
})
}
```

Example (DescendingOrder)

This example demonstrates searching a list sorted in descending order. The approach is the same as searching a list in ascending order, but with the condition inverted.

```found 6 at index 7 in [55 45 36 28 21 15 10 6 3 1]
```

## func SearchFloat64s¶

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

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.

Example

This example demonstrates searching for float64 in a list sorted in ascending order.

```found 2 at index 1 in [1 2 3.3 4.6 6.1 7.2 8]
0.5 not found, can be inserted at index 0 in [1 2 3.3 4.6 6.1 7.2 8]
```

## func SearchInts¶

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

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.

Example

This example demonstrates searching for int in a list sorted in ascending order.

```found 2 at index 1 in [1 2 3 4 6 7 8]
5 not found, can be inserted at index 4 in [1 2 3 4 6 7 8]
```

## func SearchStrings¶

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

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 Slice¶1.8

`func Slice(x interface{}, less func(i, j int) bool)`

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.

Example

```By name: [{Alice 55} {Bob 75} {Gopher 7} {Vera 24}]
By age: [{Gopher 7} {Vera 24} {Alice 55} {Bob 75}]
```

## func SliceIsSorted¶1.8

`func SliceIsSorted(x interface{}, less func(i, j int) bool) bool`

SliceIsSorted reports whether the slice x is sorted according to the provided less function. It panics if x is not a slice.

## func SliceStable¶1.8

`func SliceStable(x interface{}, less func(i, j int) bool)`

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.

Example

```By name: [{Alice 25} {Alice 75} {Alice 75} {Bob 75} {Bob 25} {Colin 25} {Elizabeth 75} {Elizabeth 25}]
By age,name: [{Alice 25} {Bob 25} {Colin 25} {Elizabeth 25} {Alice 75} {Alice 75} {Bob 75} {Elizabeth 75}]
```

## func Sort¶

`func Sort(data Interface)`

Sort sorts data. 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 Stable¶1.2

`func Stable(data Interface)`

Stable sorts data 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.

## func Strings¶

`func Strings(x []string)`

Strings sorts a slice of strings in increasing order.

Example

```[Alpha Bravo Delta Go Gopher Grin]
```

## func StringsAreSorted¶

`func StringsAreSorted(x []string) bool`

StringsAreSorted reports whether the slice x is sorted in increasing order.

## type Float64Slice¶

Float64Slice implements Interface for a []float64, sorting in increasing order, with not-a-number (NaN) values ordered before other values.

`type Float64Slice []float64`

### func (Float64Slice) Len¶

`func (x Float64Slice) Len() int`

### func (Float64Slice) Less¶

`func (x Float64Slice) Less(i, j int) bool`

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 (Float64Slice) Search¶

`func (p Float64Slice) Search(x float64) int`

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

### func (Float64Slice) Sort¶

`func (x Float64Slice) Sort()`

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

### func (Float64Slice) Swap¶

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

## type IntSlice¶

IntSlice attaches the methods of Interface to []int, sorting in increasing order.

`type IntSlice []int`

### func (IntSlice) Len¶

`func (x IntSlice) Len() int`

### func (IntSlice) Less¶

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

### func (IntSlice) Search¶

`func (p IntSlice) Search(x int) int`

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

### func (IntSlice) Sort¶

`func (x IntSlice) Sort()`

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

### func (IntSlice) Swap¶

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

## type Interface¶

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
// 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)
}```

### func Reverse¶1.1

`func Reverse(data Interface) Interface`

Reverse returns the reverse order for data.

Example

```[6 5 4 3 2 1]
```

## type StringSlice¶

StringSlice attaches the methods of Interface to []string, sorting in increasing order.

`type StringSlice []string`

### func (StringSlice) Len¶

`func (x StringSlice) Len() int`

### func (StringSlice) Less¶

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

### func (StringSlice) Search¶

`func (p StringSlice) Search(x string) int`

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

### func (StringSlice) Sort¶

`func (x StringSlice) Sort()`

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

### func (StringSlice) Swap¶

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