go: github.com/golang/go/src/sort

## package sort

`import "github.com/golang/go/src/sort"`

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

Code:

```package main

import (
"fmt"
"sort"
)

type Person struct {
Name string
Age  int
}

func (p Person) String() string {
return fmt.Sprintf("%s: %d", p.Name, p.Age)
}

// ByAge implements sort.Interface for []Person based on
// the Age field.
type ByAge []Person

func (a ByAge) Len() int           { return len(a) }
func (a ByAge) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }

func main() {
people := []Person{
{"Bob", 31},
{"John", 42},
{"Michael", 17},
{"Jenny", 26},
}

fmt.Println(people)
// There are two ways to sort a slice. First, one can define
// a set of methods for the slice type, as with ByAge, and
// call sort.Sort. In this first example we use that technique.
sort.Sort(ByAge(people))
fmt.Println(people)

// The other way is to use sort.Slice with a custom Less
// function, which can be provided as a closure. In this
// case no methods are needed. (And if they exist, they
// are ignored.) Here we re-sort in reverse order: compare
// the closure with ByAge.Less.
sort.Slice(people, func(i, j int) bool {
return people[i].Age > people[j].Age
})
fmt.Println(people)

}
```

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

Code:

```package main

import (
"fmt"
"sort"
)

// A couple of type definitions to make the units clear.
type earthMass float64
type au float64

// A Planet defines the properties of a solar system object.
type Planet struct {
name     string
mass     earthMass
distance au
}

// By is the type of a "less" function that defines the ordering of its Planet arguments.
type By func(p1, p2 *Planet) bool

// Sort is a method on the function type, By, that sorts the argument slice according to the function.
func (by By) Sort(planets []Planet) {
ps := &planetSorter{
planets: planets,
by:      by, // The Sort method's receiver is the function (closure) that defines the sort order.
}
sort.Sort(ps)
}

// planetSorter joins a By function and a slice of Planets to be sorted.
type planetSorter struct {
planets []Planet
by      func(p1, p2 *Planet) bool // Closure used in the Less method.
}

// Len is part of sort.Interface.
func (s *planetSorter) Len() int {
return len(s.planets)
}

// Swap is part of sort.Interface.
func (s *planetSorter) Swap(i, j int) {
s.planets[i], s.planets[j] = s.planets[j], s.planets[i]
}

// Less is part of sort.Interface. It is implemented by calling the "by" closure in the sorter.
func (s *planetSorter) Less(i, j int) bool {
return s.by(&s.planets[i], &s.planets[j])
}

var planets = []Planet{
{"Mercury", 0.055, 0.4},
{"Venus", 0.815, 0.7},
{"Earth", 1.0, 1.0},
{"Mars", 0.107, 1.5},
}

// ExampleSortKeys demonstrates a technique for sorting a struct type using programmable sort criteria.
func main() {
// Closures that order the Planet structure.
name := func(p1, p2 *Planet) bool {
return p1.name < p2.name
}
mass := func(p1, p2 *Planet) bool {
return p1.mass < p2.mass
}
distance := func(p1, p2 *Planet) bool {
return p1.distance < p2.distance
}
decreasingDistance := func(p1, p2 *Planet) bool {
return distance(p2, p1)
}

// Sort the planets by the various criteria.
By(name).Sort(planets)
fmt.Println("By name:", planets)

By(mass).Sort(planets)
fmt.Println("By mass:", planets)

By(distance).Sort(planets)
fmt.Println("By distance:", planets)

By(decreasingDistance).Sort(planets)
fmt.Println("By decreasing distance:", planets)

}
```

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.

Code:

```package main

import (
"fmt"
"sort"
)

// A Change is a record of source code changes, recording user, language, and delta size.
type Change struct {
user     string
language string
lines    int
}

type lessFunc func(p1, p2 *Change) bool

// multiSorter implements the Sort interface, sorting the changes within.
type multiSorter struct {
changes []Change
less    []lessFunc
}

// Sort sorts the argument slice according to the less functions passed to OrderedBy.
func (ms *multiSorter) Sort(changes []Change) {
ms.changes = changes
sort.Sort(ms)
}

// OrderedBy returns a Sorter that sorts using the less functions, in order.
// Call its Sort method to sort the data.
func OrderedBy(less ...lessFunc) *multiSorter {
return &multiSorter{
less: less,
}
}

// Len is part of sort.Interface.
func (ms *multiSorter) Len() int {
return len(ms.changes)
}

// Swap is part of sort.Interface.
func (ms *multiSorter) Swap(i, j int) {
ms.changes[i], ms.changes[j] = ms.changes[j], ms.changes[i]
}

// Less is part of sort.Interface. It is implemented by looping along the
// less functions until it finds a comparison that discriminates between
// the two items (one is less than the other). Note that it can call the
// less functions twice per call. We could change the functions to return
// -1, 0, 1 and reduce the number of calls for greater efficiency: an
func (ms *multiSorter) Less(i, j int) bool {
p, q := &ms.changes[i], &ms.changes[j]
// Try all but the last comparison.
var k int
for k = 0; k < len(ms.less)-1; k++ {
less := ms.less[k]
switch {
case less(p, q):
// p < q, so we have a decision.
return true
case less(q, p):
// p > q, so we have a decision.
return false
}
// p == q; try the next comparison.
}
// All comparisons to here said "equal", so just return whatever
// the final comparison reports.
return ms.less[k](p, q)
}

var changes = []Change{
{"gri", "Go", 100},
{"ken", "C", 150},
{"glenda", "Go", 200},
{"rsc", "Go", 200},
{"r", "Go", 100},
{"ken", "Go", 200},
{"dmr", "C", 100},
{"r", "C", 150},
{"gri", "Smalltalk", 80},
}

// 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.
func main() {
// Closures that order the Change structure.
user := func(c1, c2 *Change) bool {
return c1.user < c2.user
}
language := func(c1, c2 *Change) bool {
return c1.language < c2.language
}
increasingLines := func(c1, c2 *Change) bool {
return c1.lines < c2.lines
}
decreasingLines := func(c1, c2 *Change) bool {
return c1.lines > c2.lines // Note: > orders downwards.
}

// Simple use: Sort by user.
OrderedBy(user).Sort(changes)
fmt.Println("By user:", changes)

// More examples.
OrderedBy(user, increasingLines).Sort(changes)
fmt.Println("By user,<lines:", changes)

OrderedBy(user, decreasingLines).Sort(changes)
fmt.Println("By user,>lines:", changes)

OrderedBy(language, increasingLines).Sort(changes)
fmt.Println("By language,<lines:", changes)

OrderedBy(language, increasingLines, user).Sort(changes)
fmt.Println("By language,<lines,user:", changes)

}
```

Code:

```package main

import (
"fmt"
"sort"
)

type Grams int

func (g Grams) String() string { return fmt.Sprintf("%dg", int(g)) }

type Organ struct {
Name   string
Weight Grams
}

type Organs []*Organ

func (s Organs) Len() int      { return len(s) }
func (s Organs) Swap(i, j int) { s[i], s[j] = s[j], s[i] }

// ByName implements sort.Interface by providing Less and using the Len and
// Swap methods of the embedded Organs value.
type ByName struct{ Organs }

func (s ByName) Less(i, j int) bool { return s.Organs[i].Name < s.Organs[j].Name }

// ByWeight implements sort.Interface by providing Less and using the Len and
// Swap methods of the embedded Organs value.
type ByWeight struct{ Organs }

func (s ByWeight) Less(i, j int) bool { return s.Organs[i].Weight < s.Organs[j].Weight }

func main() {
s := []*Organ{
{"brain", 1340},
{"heart", 290},
{"liver", 1494},
{"pancreas", 131},
{"prostate", 62},
{"spleen", 162},
}

sort.Sort(ByWeight{s})
fmt.Println("Organs by weight:")
printOrgans(s)

sort.Sort(ByName{s})
fmt.Println("Organs by name:")
printOrgans(s)

}

func printOrgans(s []*Organ) {
for _, o := range s {
fmt.Printf("%-8s (%v)\n", o.Name, o.Weight)
}
}
```

### func Float64s¶Uses

`func Float64s(a []float64)`

Float64s sorts a slice of float64s in increasing order (not-a-number values are treated as less than other values).

Code:

```s := []float64{5.2, -1.3, 0.7, -3.8, 2.6} // unsorted
sort.Float64s(s)
fmt.Println(s)

s = []float64{math.Inf(1), math.NaN(), math.Inf(-1), 0.0} // unsorted
sort.Float64s(s)
fmt.Println(s)```

Output:

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

### func Float64sAreSorted¶Uses

`func Float64sAreSorted(a []float64) bool`

Float64sAreSorted tests whether a slice of float64s is sorted in increasing order (not-a-number values are treated as less than other values).

Code:

```s := []float64{0.7, 1.3, 2.6, 3.8, 5.2} // sorted ascending
fmt.Println(sort.Float64sAreSorted(s))

s = []float64{5.2, 3.8, 2.6, 1.3, 0.7} // sorted descending
fmt.Println(sort.Float64sAreSorted(s))

s = []float64{5.2, 1.3, 0.7, 3.8, 2.6} // unsorted
fmt.Println(sort.Float64sAreSorted(s))```

Output:

```true
false
false
```

### func Ints¶Uses

`func Ints(a []int)`

Ints sorts a slice of ints in increasing order.

Code:

```s := []int{5, 2, 6, 3, 1, 4} // unsorted
sort.Ints(s)
fmt.Println(s)```

Output:

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

### func IntsAreSorted¶Uses

`func IntsAreSorted(a []int) bool`

IntsAreSorted tests whether a slice of ints is sorted in increasing order.

Code:

```s := []int{1, 2, 3, 4, 5, 6} // sorted ascending
fmt.Println(sort.IntsAreSorted(s))

s = []int{6, 5, 4, 3, 2, 1} // sorted descending
fmt.Println(sort.IntsAreSorted(s))

s = []int{3, 2, 4, 1, 5} // unsorted
fmt.Println(sort.IntsAreSorted(s))```

Output:

```true
false
false
```

### func IsSorted¶Uses

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

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.

Code:

```a := []int{55, 45, 36, 28, 21, 15, 10, 6, 3, 1}
x := 6

i := sort.Search(len(a), func(i int) bool { return a[i] <= x })
if i < len(a) && a[i] == x {
fmt.Printf("found %d at index %d in %v\n", x, i, a)
} else {
}```

Output:

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

### func SearchFloat64s¶Uses

`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.

### func SearchInts¶Uses

`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.

### func SearchStrings¶Uses

`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¶Uses

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

Slice sorts the provided slice given the provided less function.

The sort is not guaranteed to be stable. For a stable sort, use SliceStable.

The function panics if the provided interface is not a slice.

Code:

```people := []struct {
Name string
Age  int
}{
{"Gopher", 7},
{"Alice", 55},
{"Vera", 24},
{"Bob", 75},
}
sort.Slice(people, func(i, j int) bool { return people[i].Name < people[j].Name })
fmt.Println("By name:", people)

sort.Slice(people, func(i, j int) bool { return people[i].Age < people[j].Age })
fmt.Println("By age:", people)```

Output:

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

### func SliceIsSorted¶Uses

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

SliceIsSorted tests whether a slice is sorted.

The function panics if the provided interface is not a slice.

### func SliceStable¶Uses

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

SliceStable sorts the provided slice given the provided less function while keeping the original order of equal elements.

The function panics if the provided interface is not a slice.

Code:

```people := []struct {
Name string
Age  int
}{
{"Alice", 25},
{"Elizabeth", 75},
{"Alice", 75},
{"Bob", 75},
{"Alice", 75},
{"Bob", 25},
{"Colin", 25},
{"Elizabeth", 25},
}

// Sort by name, preserving original order
sort.SliceStable(people, func(i, j int) bool { return people[i].Name < people[j].Name })
fmt.Println("By name:", people)

// Sort by age preserving name order
sort.SliceStable(people, func(i, j int) bool { return people[i].Age < people[j].Age })
fmt.Println("By age,name:", people)```

Output:

```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¶Uses

`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¶Uses

`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¶Uses

`func Strings(a []string)`

Strings sorts a slice of strings in increasing order.

Code:

```s := []string{"Go", "Bravo", "Gopher", "Alpha", "Grin", "Delta"}
sort.Strings(s)
fmt.Println(s)```

Output:

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

### func StringsAreSorted¶Uses

`func StringsAreSorted(a []string) bool`

StringsAreSorted tests whether a slice of strings is sorted in increasing order.

### type Float64Slice¶Uses

`type Float64Slice []float64`

Float64Slice attaches the methods of Interface to []float64, sorting in increasing order (not-a-number values are treated as less than other values).

#### func (Float64Slice) Len¶Uses

`func (p Float64Slice) Len() int`

#### func (Float64Slice) Less¶Uses

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

#### func (Float64Slice) Search¶Uses

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

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

#### func (Float64Slice) Sort¶Uses

`func (p Float64Slice) Sort()`

Sort is a convenience method.

#### func (Float64Slice) Swap¶Uses

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

### type IntSlice¶Uses

`type IntSlice []int`

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

#### func (IntSlice) Len¶Uses

`func (p IntSlice) Len() int`

#### func (IntSlice) Less¶Uses

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

#### func (IntSlice) Search¶Uses

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

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

#### func (IntSlice) Sort¶Uses

`func (p IntSlice) Sort()`

Sort is a convenience method.

#### func (IntSlice) Swap¶Uses

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

### type Interface¶Uses

```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(i, j int) bool
// Swap swaps the elements with indexes i and j.
Swap(i, j int)
}```

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.

#### func Reverse¶Uses

`func Reverse(data Interface) Interface`

Reverse returns the reverse order for data.

Code:

```s := []int{5, 2, 6, 3, 1, 4} // unsorted
sort.Sort(sort.Reverse(sort.IntSlice(s)))
fmt.Println(s)```

Output:

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

### type StringSlice¶Uses

`type StringSlice []string`

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

#### func (StringSlice) Len¶Uses

`func (p StringSlice) Len() int`

#### func (StringSlice) Less¶Uses

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

#### func (StringSlice) Search¶Uses

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

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

#### func (StringSlice) Sort¶Uses

`func (p StringSlice) Sort()`

Sort is a convenience method.

#### func (StringSlice) Swap¶Uses

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

Package sort imports 1 packages (graph) and is imported by 1 packages. Updated 2019-05-19. Refresh now. Tools for package owners.