package sort

Import Path
	sort (on go.dev)

Dependency Relation
	imports 3 packages, and imported by 52 packages

Involved Source Files search.go slice.go Package sort provides primitives for sorting slices and user-defined collections. sort_impl_go121.go zsortfunc.go zsortinterface.go
Code Examples 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) } package main import ( "fmt" "math" "sort" ) func main() { 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) } package main import ( "fmt" "sort" ) func main() { 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)) } package main import ( "fmt" "sort" ) func main() { s := []int{5, 2, 6, 3, 1, 4} // unsorted sort.Ints(s) fmt.Println(s) } package main import ( "fmt" "sort" ) func main() { 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)) } package main import ( "fmt" "sort" ) func main() { s := []int{5, 2, 6, 3, 1, 4} // unsorted sort.Sort(sort.Reverse(sort.IntSlice(s))) fmt.Println(s) } package main import ( "fmt" "sort" ) func main() { a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55} 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 { fmt.Printf("%d not found in %v\n", x, a) } } package main import ( "fmt" "sort" ) func main() { a := []float64{1.0, 2.0, 3.3, 4.6, 6.1, 7.2, 8.0} x := 2.0 i := sort.SearchFloat64s(a, x) fmt.Printf("found %g at index %d in %v\n", x, i, a) x = 0.5 i = sort.SearchFloat64s(a, x) fmt.Printf("%g not found, can be inserted at index %d in %v\n", x, i, a) } package main import ( "fmt" "sort" ) func main() { a := []int{1, 2, 3, 4, 6, 7, 8} x := 2 i := sort.SearchInts(a, x) fmt.Printf("found %d at index %d in %v\n", x, i, a) x = 5 i = sort.SearchInts(a, x) fmt.Printf("%d not found, can be inserted at index %d in %v\n", x, i, a) } package main import ( "fmt" "sort" ) func main() { 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 { fmt.Printf("%d not found in %v\n", x, a) } } package main import ( "fmt" "sort" ) func main() { 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) } package main import ( "fmt" "sort" ) func main() { 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) } package main import ( "fmt" "sort" ) func main() { s := []string{"Go", "Bravo", "Gopher", "Alpha", "Grin", "Delta"} sort.Strings(s) fmt.Println(s) } 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) } 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 // exercise for the reader. 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) } 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) } }
Package-Level Type Names (total 4)
/* sort by: | */
Float64Slice implements Interface for a []float64, sorting in increasing order, with not-a-number (NaN) values ordered before other values. ( Float64Slice) Len() int 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])) Search returns the result of applying [SearchFloat64s] to the receiver and x. Sort is a convenience method: x.Sort() calls Sort(x). ( Float64Slice) Swap(i, j int) Float64Slice : 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. Len is the number of elements in the collection. 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. Swap swaps the elements with indexes i and j. Float64Slice IntSlice StringSlice container/heap.Interface (interface) go/scanner.ErrorList *internal/fmtsort.SortedMap func Reverse(data Interface) Interface func IsSorted(data Interface) bool func Reverse(data Interface) Interface func Sort(data Interface) func Stable(data Interface)
IntSlice attaches the methods of Interface to []int, sorting in increasing order. ( IntSlice) Len() int ( IntSlice) Less(i, j int) bool Search returns the result of applying [SearchInts] to the receiver and x. Sort is a convenience method: x.Sort() calls Sort(x). ( IntSlice) Swap(i, j int) IntSlice : Interface
StringSlice attaches the methods of Interface to []string, sorting in increasing order. ( StringSlice) Len() int ( StringSlice) Less(i, j int) bool Search returns the result of applying [SearchStrings] to the receiver and x. Sort is a convenience method: x.Sort() calls Sort(x). ( StringSlice) Swap(i, j int) StringSlice : Interface
Package-Level Functions (total 18)
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) }
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].
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].
Ints sorts a slice of ints in increasing order. Note: as of Go 1.22, this function simply calls [slices.Sort].
IntsAreSorted reports whether the slice x is sorted in increasing order. Note: as of Go 1.22, this function simply calls [slices.IsSorted].
IsSorted reports whether data is sorted. Note: in many situations, the newer [slices.IsSortedFunc] function is more ergonomic and runs faster.
Reverse returns the reverse order for data.
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.
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.
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.
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.
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.
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.
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.
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.
Strings sorts a slice of strings in increasing order. Note: as of Go 1.22, this function simply calls [slices.Sort].
StringsAreSorted reports whether the slice x is sorted in increasing order. Note: as of Go 1.22, this function simply calls [slices.IsSorted].