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 := []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(language, increasingLines).Sort(changes)
fmt.Println("By language,
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 6, in which 4 are exported)
/* sort exporteds by: | */
Float64Slice implements Interface for a []float64, sorting in increasing order,
with not-a-number (NaN) values ordered before other values.
( T) 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).
( T) Swap(i, j int)
T : 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.
Float64SliceIntSliceStringSlice
*github.com/golang/protobuf/proto.StructProperties
github.com/hashicorp/hcl/hcl/printer.ByPosition
github.com/trivago/tgo/tcontainer.Float32Slice
github.com/trivago/tgo/tcontainer.Int64Slice
github.com/trivago/tgo/tcontainer.Uint64Slice
*internal/fmtsort.SortedMapreverse
compress/flate.byFreq
compress/flate.byLiteral
encoding/json.byIndex
github.com/jedib0t/go-pretty/v6/table.rowsSorter
github.com/json-iterator/go.encodedKeyValues
github.com/json-iterator/go.sortableBindings
github.com/juju/ansiterm.attributes
github.com/spf13/afero.byName
github.com/spf13/afero/mem.filesSorter
github.com/spf13/cobra.commandSorterByName
gopkg.in/natefinch/lumberjack.v2.byFormatTime
gopkg.in/yaml.v2.keyList
gopkg.in/yaml.v3.keyList
net.byMaskLength
net.byPref
net.byPriorityWeight
*net.byRFC6724
*net/http.headerSorter
*net/http.http2sorter
net/http.http2sortPriorityNodeSiblings
regexp.runeSlice
regexp/syntax.ranges
vendor/golang.org/x/text/unicode/bidi.bracketPairs
func Reverse(data Interface) Interface
func IsSorted(data Interface) bool
func Reverse(data Interface) Interface
func Sort(data Interface)
func Stable(data Interface)
func doPivot(data Interface, lo, hi int) (midlo, midhi int)
func heapSort(data Interface, a, b int)
func insertionSort(data Interface, a, b int)
func medianOfThree(data Interface, m1, m0, m2 int)
func quickSort(data Interface, a, b, maxDepth int)
func rotate(data Interface, a, m, b int)
func siftDown(data Interface, lo, hi, first int)
func stable(data Interface, n int)
func swapRange(data Interface, a, b, n int)
func symMerge(data Interface, a, m, b int)
IntSlice attaches the methods of Interface to []int, sorting in increasing order.
( T) Len() int( T) 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).
( T) Swap(i, j int)
T : Interface
StringSlice attaches the methods of Interface to []string, sorting in increasing order.
( T) Len() int( T) 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).
( T) Swap(i, j int)
T : Interface
This embedded Interface permits Reverse to use the methods of
another Interface implementation.
Len is the number of elements in the collection.
Less returns the opposite of the embedded implementation's Less method.
Swap swaps the elements with indexes i and j.
T : Interface
Package-Level Functions (total 39, in which 17 are exported)
Float64s sorts a slice of float64s in increasing order.
Not-a-number (NaN) values are ordered before other values.
Float64sAreSorted reports whether the slice x is sorted in increasing order,
with not-a-number (NaN) values before any other values.
Ints sorts a slice of ints in increasing order.
IntsAreSorted reports whether the slice x is sorted in increasing order.
IsSorted reports whether data is sorted.
Reverse returns the reverse order for data.
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)
}
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.
SliceIsSorted reports whether the slice x is sorted according to the provided less function.
It panics if x is not a slice.
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.
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.
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.
Strings sorts a slice of strings in increasing order.
StringsAreSorted reports whether the slice x is sorted in increasing order.
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.
Auto-generated variant of sort.go:rotate
siftDown implements the heap property on data[lo:hi].
first is an offset into the array where the root of the heap lies.
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.
Auto-generated variant of sort.go:symMerge
Package-Level Variables (total 2, neither is exported)
The pages are generated with Goldsv0.3.2. (GOOS=linux GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu.
PR and bug reports are welcome and can be submitted to the issue list.
Please follow @Go100and1 (reachable from the left QR code) to get the latest news of Golds.
