path: root/devdocs/go/sort%2Findex.html

<h1> Package sort  </h1>     <ul id="short-nav">
<li><code>import "sort"</code></li>
<li><a href="#pkg-overview" class="overviewLink">Overview</a></li>
<li><a href="#pkg-index" class="indexLink">Index</a></li>
<li><a href="#pkg-examples" class="examplesLink">Examples</a></li>
</ul>     <h2 id="pkg-overview">Overview </h2> <p>Package sort provides primitives for sorting slices and user-defined collections. </p>   <h4 id="example_"> <span class="text">Example</span>
</h4> <p>Code:</p> <pre class="code" data-language="go">package sort_test

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 &lt; a[j].Age }

func Example() {
    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 &gt; people[j].Age
    })
    fmt.Println(people)

    // Output:
    // [Bob: 31 John: 42 Michael: 17 Jenny: 26]
    // [Michael: 17 Jenny: 26 Bob: 31 John: 42]
    // [John: 42 Bob: 31 Jenny: 26 Michael: 17]
}
</pre>      <h4 id="example__sortKeys"> <span class="text">Example (SortKeys)</span>
</h4> <p>ExampleSortKeys demonstrates a technique for sorting a struct type using programmable sort criteria. </p> <p>Code:</p> <pre class="code" data-language="go">package sort_test

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 := &amp;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(&amp;s.planets[i], &amp;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 Example_sortKeys() {
    // Closures that order the Planet structure.
    name := func(p1, p2 *Planet) bool {
        return p1.name &lt; p2.name
    }
    mass := func(p1, p2 *Planet) bool {
        return p1.mass &lt; p2.mass
    }
    distance := func(p1, p2 *Planet) bool {
        return p1.distance &lt; 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)

    // Output: 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}]
}
</pre>      <h4 id="example__sortMultiKeys"> <span class="text">Example (SortMultiKeys)</span>
</h4> <p>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. </p> <p>Code:</p> <pre class="code" data-language="go">package sort_test

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 &amp;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 := &amp;ms.changes[i], &amp;ms.changes[j]
    // Try all but the last comparison.
    var k int
    for k = 0; k &lt; len(ms.less)-1; k++ {
        less := ms.less[k]
        switch {
        case less(p, q):
            // p &lt; q, so we have a decision.
            return true
        case less(q, p):
            // p &gt; 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 Example_sortMultiKeys() {
    // Closures that order the Change structure.
    user := func(c1, c2 *Change) bool {
        return c1.user &lt; c2.user
    }
    language := func(c1, c2 *Change) bool {
        return c1.language &lt; c2.language
    }
    increasingLines := func(c1, c2 *Change) bool {
        return c1.lines &lt; c2.lines
    }
    decreasingLines := func(c1, c2 *Change) bool {
        return c1.lines &gt; c2.lines // Note: &gt; 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,&lt;lines:", changes)

    OrderedBy(user, decreasingLines).Sort(changes)
    fmt.Println("By user,&gt;lines:", changes)

    OrderedBy(language, increasingLines).Sort(changes)
    fmt.Println("By language,&lt;lines:", changes)

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

    // Output:
    // 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,&lt;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,&gt;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,&lt;lines: [{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}]
    // By language,&lt;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}]

}
</pre>      <h4 id="example__sortWrapper"> <span class="text">Example (SortWrapper)</span>
</h4> <p>Code:</p> <pre class="code" data-language="go">package sort_test

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 &lt; 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 &lt; s.Organs[j].Weight }

func Example_sortWrapper() {
    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)

    // Output:
    // 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 printOrgans(s []*Organ) {
    for _, o := range s {
        fmt.Printf("%-8s (%v)\n", o.Name, o.Weight)
    }
}
</pre>        <h2 id="pkg-index">Index </h2>  <ul id="manual-nav">
<li><a href="#Find">func Find(n int, cmp func(int) int) (i int, found bool)</a></li>
<li><a href="#Float64s">func Float64s(x []float64)</a></li>
<li><a href="#Float64sAreSorted">func Float64sAreSorted(x []float64) bool</a></li>
<li><a href="#Ints">func Ints(x []int)</a></li>
<li><a href="#IntsAreSorted">func IntsAreSorted(x []int) bool</a></li>
<li><a href="#IsSorted">func IsSorted(data Interface) bool</a></li>
<li><a href="#Search">func Search(n int, f func(int) bool) int</a></li>
<li><a href="#SearchFloat64s">func SearchFloat64s(a []float64, x float64) int</a></li>
<li><a href="#SearchInts">func SearchInts(a []int, x int) int</a></li>
<li><a href="#SearchStrings">func SearchStrings(a []string, x string) int</a></li>
<li><a href="#Slice">func Slice(x any, less func(i, j int) bool)</a></li>
<li><a href="#SliceIsSorted">func SliceIsSorted(x any, less func(i, j int) bool) bool</a></li>
<li><a href="#SliceStable">func SliceStable(x any, less func(i, j int) bool)</a></li>
<li><a href="#Sort">func Sort(data Interface)</a></li>
<li><a href="#Stable">func Stable(data Interface)</a></li>
<li><a href="#Strings">func Strings(x []string)</a></li>
<li><a href="#StringsAreSorted">func StringsAreSorted(x []string) bool</a></li>
<li><a href="#Float64Slice">type Float64Slice</a></li>
<li> <a href="#Float64Slice.Len">func (x Float64Slice) Len() int</a>
</li>
<li> <a href="#Float64Slice.Less">func (x Float64Slice) Less(i, j int) bool</a>
</li>
<li> <a href="#Float64Slice.Search">func (p Float64Slice) Search(x float64) int</a>
</li>
<li> <a href="#Float64Slice.Sort">func (x Float64Slice) Sort()</a>
</li>
<li> <a href="#Float64Slice.Swap">func (x Float64Slice) Swap(i, j int)</a>
</li>
<li><a href="#IntSlice">type IntSlice</a></li>
<li> <a href="#IntSlice.Len">func (x IntSlice) Len() int</a>
</li>
<li> <a href="#IntSlice.Less">func (x IntSlice) Less(i, j int) bool</a>
</li>
<li> <a href="#IntSlice.Search">func (p IntSlice) Search(x int) int</a>
</li>
<li> <a href="#IntSlice.Sort">func (x IntSlice) Sort()</a>
</li>
<li> <a href="#IntSlice.Swap">func (x IntSlice) Swap(i, j int)</a>
</li>
<li><a href="#Interface">type Interface</a></li>
<li> <a href="#Reverse">func Reverse(data Interface) Interface</a>
</li>
<li><a href="#StringSlice">type StringSlice</a></li>
<li> <a href="#StringSlice.Len">func (x StringSlice) Len() int</a>
</li>
<li> <a href="#StringSlice.Less">func (x StringSlice) Less(i, j int) bool</a>
</li>
<li> <a href="#StringSlice.Search">func (p StringSlice) Search(x string) int</a>
</li>
<li> <a href="#StringSlice.Sort">func (x StringSlice) Sort()</a>
</li>
<li> <a href="#StringSlice.Swap">func (x StringSlice) Swap(i, j int)</a>
</li>
</ul> <div id="pkg-examples"> <h3>Examples</h3>  <dl> <dd><a class="exampleLink" href="#example_">Package</a></dd> <dd><a class="exampleLink" href="#example_Float64s">Float64s</a></dd> <dd><a class="exampleLink" href="#example_Float64sAreSorted">Float64sAreSorted</a></dd> <dd><a class="exampleLink" href="#example_Ints">Ints</a></dd> <dd><a class="exampleLink" href="#example_IntsAreSorted">IntsAreSorted</a></dd> <dd><a class="exampleLink" href="#example_Reverse">Reverse</a></dd> <dd><a class="exampleLink" href="#example_Search">Search</a></dd> <dd><a class="exampleLink" href="#example_SearchFloat64s">SearchFloat64s</a></dd> <dd><a class="exampleLink" href="#example_SearchInts">SearchInts</a></dd> <dd><a class="exampleLink" href="#example_Search_descendingOrder">Search (DescendingOrder)</a></dd> <dd><a class="exampleLink" href="#example_Slice">Slice</a></dd> <dd><a class="exampleLink" href="#example_SliceStable">SliceStable</a></dd> <dd><a class="exampleLink" href="#example_Strings">Strings</a></dd> <dd><a class="exampleLink" href="#example__sortKeys">Package (SortKeys)</a></dd> <dd><a class="exampleLink" href="#example__sortMultiKeys">Package (SortMultiKeys)</a></dd> <dd><a class="exampleLink" href="#example__sortWrapper">Package (SortWrapper)</a></dd> </dl> </div> <h3>Package files</h3> <p>  <span>search.go</span> <span>slice.go</span> <span>sort.go</span> <span>sort_impl_go121.go</span> <span>zsortfunc.go</span> <span>zsortinterface.go</span>  </p>   <h2 id="Find">func <span>Find</span>  <span title="Added in Go 1.19">1.19</span> </h2> <pre data-language="go">func Find(n int, cmp func(int) int) (i int, found bool)</pre> <p>Find uses binary search to find and return the smallest index i in [0, n) at which cmp(i) &lt;= 0. If there is no such index i, Find returns i = n. The found result is true if i &lt; n and cmp(i) == 0. Find calls cmp(i) only for i in the range [0, n). </p>
<p>To permit binary search, Find requires that cmp(i) &gt; 0 for a leading prefix of the range, cmp(i) == 0 in the middle, and cmp(i) &lt; 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 &lt;0, 0, and &gt;0 when t &lt; x[i], t == x[i], and t &gt; x[i], respectively. </p>
<p>For example, to look for a particular string in a sorted, random-access list of strings: </p>
<pre data-language="go">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)
}
</pre> <h2 id="Float64s">func <span>Float64s</span>  </h2> <pre data-language="go">func Float64s(x []float64)</pre> <p>Float64s sorts a slice of float64s in increasing order. Not-a-number (NaN) values are ordered before other values. </p>
<p>Note: as of Go 1.22, this function simply calls <span>slices.Sort</span>. </p>   <h4 id="example_Float64s"> <span class="text">Example</span>
</h4> <p>Code:</p> <pre class="code" data-language="go">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)

</pre> <p>Output:</p> <pre class="output" data-language="go">[-3.8 -1.3 0.7 2.6 5.2]
[NaN -Inf 0 +Inf]
</pre>   <h2 id="Float64sAreSorted">func <span>Float64sAreSorted</span>  </h2> <pre data-language="go">func Float64sAreSorted(x []float64) bool</pre> <p>Float64sAreSorted reports whether the slice x is sorted in increasing order, with not-a-number (NaN) values before any other values. </p>
<p>Note: as of Go 1.22, this function simply calls <span>slices.IsSorted</span>. </p>   <h4 id="example_Float64sAreSorted"> <span class="text">Example</span>
</h4> <p>Code:</p> <pre class="code" data-language="go">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))

</pre> <p>Output:</p> <pre class="output" data-language="go">true
false
false
</pre>   <h2 id="Ints">func <span>Ints</span>  </h2> <pre data-language="go">func Ints(x []int)</pre> <p>Ints sorts a slice of ints in increasing order. </p>
<p>Note: as of Go 1.22, this function simply calls <span>slices.Sort</span>. </p>   <h4 id="example_Ints"> <span class="text">Example</span>
</h4> <p>Code:</p> <pre class="code" data-language="go">s := []int{5, 2, 6, 3, 1, 4} // unsorted
sort.Ints(s)
fmt.Println(s)
</pre> <p>Output:</p> <pre class="output" data-language="go">[1 2 3 4 5 6]
</pre>   <h2 id="IntsAreSorted">func <span>IntsAreSorted</span>  </h2> <pre data-language="go">func IntsAreSorted(x []int) bool</pre> <p>IntsAreSorted reports whether the slice x is sorted in increasing order. </p>
<p>Note: as of Go 1.22, this function simply calls <span>slices.IsSorted</span>. </p>   <h4 id="example_IntsAreSorted"> <span class="text">Example</span>
</h4> <p>Code:</p> <pre class="code" data-language="go">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))

</pre> <p>Output:</p> <pre class="output" data-language="go">true
false
false
</pre>   <h2 id="IsSorted">func <span>IsSorted</span>  </h2> <pre data-language="go">func IsSorted(data Interface) bool</pre> <p>IsSorted reports whether data is sorted. </p>
<p>Note: in many situations, the newer <span>slices.IsSortedFunc</span> function is more ergonomic and runs faster. </p>
<h2 id="Search">func <span>Search</span>  </h2> <pre data-language="go">func Search(n int, f func(int) bool) int</pre> <p>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). </p>
<p>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. </p>
<p>For instance, given a slice data sorted in ascending order, the call Search(len(data), func(i int) bool { return data[i] &gt;= 23 }) returns the smallest index i such that data[i] &gt;= 23. If the caller wants to find whether 23 is in the slice, it must test data[i] == 23 separately. </p>
<p>Searching data sorted in descending order would use the &lt;= operator instead of the &gt;= operator. </p>
<p>To complete the example above, the following code tries to find the value x in an integer slice data sorted in ascending order: </p>
<pre data-language="go">x := 23
i := sort.Search(len(data), func(i int) bool { return data[i] &gt;= x })
if i &lt; len(data) &amp;&amp; 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.
}
</pre> <p>As a more whimsical example, this program guesses your number: </p>
<pre data-language="go">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 &lt;= %d? ", i)
		fmt.Scanf("%s", &amp;s)
		return s != "" &amp;&amp; s[0] == 'y'
	})
	fmt.Printf("Your number is %d.\n", answer)
}
</pre>    <h4 id="example_Search"> <span class="text">Example</span>
</h4> <p>This example demonstrates searching a list sorted in ascending order. </p> <p>Code:</p> <pre class="code" data-language="go">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] &gt;= x })
if i &lt; len(a) &amp;&amp; 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)
}
</pre> <p>Output:</p> <pre class="output" data-language="go">found 6 at index 2 in [1 3 6 10 15 21 28 36 45 55]
</pre>      <h4 id="example_Search_descendingOrder"> <span class="text">Example (DescendingOrder)</span>
</h4> <p>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. </p> <p>Code:</p> <pre class="code" data-language="go">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] &lt;= x })
if i &lt; len(a) &amp;&amp; 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)
}
</pre> <p>Output:</p> <pre class="output" data-language="go">found 6 at index 7 in [55 45 36 28 21 15 10 6 3 1]
</pre>   <h2 id="SearchFloat64s">func <span>SearchFloat64s</span>  </h2> <pre data-language="go">func SearchFloat64s(a []float64, x float64) int</pre> <p>SearchFloat64s searches for x in a sorted slice of float64s and returns the index as specified by <a href="#Search">Search</a>. 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. </p>   <h4 id="example_SearchFloat64s"> <span class="text">Example</span>
</h4> <p>This example demonstrates searching for float64 in a list sorted in ascending order. </p> <p>Code:</p> <pre class="code" data-language="go">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)
</pre> <p>Output:</p> <pre class="output" data-language="go">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]
</pre>   <h2 id="SearchInts">func <span>SearchInts</span>  </h2> <pre data-language="go">func SearchInts(a []int, x int) int</pre> <p>SearchInts searches for x in a sorted slice of ints and returns the index as specified by <a href="#Search">Search</a>. 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. </p>   <h4 id="example_SearchInts"> <span class="text">Example</span>
</h4> <p>This example demonstrates searching for int in a list sorted in ascending order. </p> <p>Code:</p> <pre class="code" data-language="go">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)
</pre> <p>Output:</p> <pre class="output" data-language="go">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]
</pre>   <h2 id="SearchStrings">func <span>SearchStrings</span>  </h2> <pre data-language="go">func SearchStrings(a []string, x string) int</pre> <p>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. </p>
<h2 id="Slice">func <span>Slice</span>  <span title="Added in Go 1.8">1.8</span> </h2> <pre data-language="go">func Slice(x any, less func(i, j int) bool)</pre> <p>Slice sorts the slice x given the provided less function. It panics if x is not a slice. </p>
<p>The sort is not guaranteed to be stable: equal elements may be reversed from their original order. For a stable sort, use <a href="#SliceStable">SliceStable</a>. </p>
<p>The less function must satisfy the same requirements as the Interface type's Less method. </p>
<p>Note: in many situations, the newer <span>slices.SortFunc</span> function is more ergonomic and runs faster. </p>   <h4 id="example_Slice"> <span class="text">Example</span>
</h4> <p>Code:</p> <pre class="code" data-language="go">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 &lt; people[j].Name })
fmt.Println("By name:", people)

sort.Slice(people, func(i, j int) bool { return people[i].Age &lt; people[j].Age })
fmt.Println("By age:", people)
</pre> <p>Output:</p> <pre class="output" data-language="go">By name: [{Alice 55} {Bob 75} {Gopher 7} {Vera 24}]
By age: [{Gopher 7} {Vera 24} {Alice 55} {Bob 75}]
</pre>   <h2 id="SliceIsSorted">func <span>SliceIsSorted</span>  <span title="Added in Go 1.8">1.8</span> </h2> <pre data-language="go">func SliceIsSorted(x any, less func(i, j int) bool) bool</pre> <p>SliceIsSorted reports whether the slice x is sorted according to the provided less function. It panics if x is not a slice. </p>
<p>Note: in many situations, the newer <span>slices.IsSortedFunc</span> function is more ergonomic and runs faster. </p>
<h2 id="SliceStable">func <span>SliceStable</span>  <span title="Added in Go 1.8">1.8</span> </h2> <pre data-language="go">func SliceStable(x any, less func(i, j int) bool)</pre> <p>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. </p>
<p>The less function must satisfy the same requirements as the Interface type's Less method. </p>
<p>Note: in many situations, the newer <span>slices.SortStableFunc</span> function is more ergonomic and runs faster. </p>   <h4 id="example_SliceStable"> <span class="text">Example</span>
</h4> <p>Code:</p> <pre class="code" data-language="go">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 &lt; 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 &lt; people[j].Age })
fmt.Println("By age,name:", people)

</pre> <p>Output:</p> <pre class="output" data-language="go">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}]
</pre>   <h2 id="Sort">func <span>Sort</span>  </h2> <pre data-language="go">func Sort(data Interface)</pre> <p>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. </p>
<p>Note: in many situations, the newer <span>slices.SortFunc</span> function is more ergonomic and runs faster. </p>
<h2 id="Stable">func <span>Stable</span>  <span title="Added in Go 1.2">1.2</span> </h2> <pre data-language="go">func Stable(data Interface)</pre> <p>Stable sorts data in ascending order as determined by the Less method, while keeping the original order of equal elements. </p>
<p>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. </p>
<p>Note: in many situations, the newer slices.SortStableFunc function is more ergonomic and runs faster. </p>
<h2 id="Strings">func <span>Strings</span>  </h2> <pre data-language="go">func Strings(x []string)</pre> <p>Strings sorts a slice of strings in increasing order. </p>
<p>Note: as of Go 1.22, this function simply calls <span>slices.Sort</span>. </p>   <h4 id="example_Strings"> <span class="text">Example</span>
</h4> <p>Code:</p> <pre class="code" data-language="go">s := []string{"Go", "Bravo", "Gopher", "Alpha", "Grin", "Delta"}
sort.Strings(s)
fmt.Println(s)
</pre> <p>Output:</p> <pre class="output" data-language="go">[Alpha Bravo Delta Go Gopher Grin]
</pre>   <h2 id="StringsAreSorted">func <span>StringsAreSorted</span>  </h2> <pre data-language="go">func StringsAreSorted(x []string) bool</pre> <p>StringsAreSorted reports whether the slice x is sorted in increasing order. </p>
<p>Note: as of Go 1.22, this function simply calls <span>slices.IsSorted</span>. </p>
<h2 id="Float64Slice">type <span>Float64Slice</span>  </h2> <p>Float64Slice implements Interface for a []float64, sorting in increasing order, with not-a-number (NaN) values ordered before other values. </p>
<pre data-language="go">type Float64Slice []float64</pre> <h3 id="Float64Slice.Len">func (Float64Slice) <span>Len</span>  </h3> <pre data-language="go">func (x Float64Slice) Len() int</pre> <h3 id="Float64Slice.Less">func (Float64Slice) <span>Less</span>  </h3> <pre data-language="go">func (x Float64Slice) Less(i, j int) bool</pre> <p>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: </p>
<pre data-language="go">x[i] &lt; x[j] || (math.IsNaN(x[i]) &amp;&amp; !math.IsNaN(x[j]))
</pre> <h3 id="Float64Slice.Search">func (Float64Slice) <span>Search</span>  </h3> <pre data-language="go">func (p Float64Slice) Search(x float64) int</pre> <p>Search returns the result of applying <a href="#SearchFloat64s">SearchFloat64s</a> to the receiver and x. </p>
<h3 id="Float64Slice.Sort">func (Float64Slice) <span>Sort</span>  </h3> <pre data-language="go">func (x Float64Slice) Sort()</pre> <p>Sort is a convenience method: x.Sort() calls Sort(x). </p>
<h3 id="Float64Slice.Swap">func (Float64Slice) <span>Swap</span>  </h3> <pre data-language="go">func (x Float64Slice) Swap(i, j int)</pre> <h2 id="IntSlice">type <span>IntSlice</span>  </h2> <p>IntSlice attaches the methods of Interface to []int, sorting in increasing order. </p>
<pre data-language="go">type IntSlice []int</pre> <h3 id="IntSlice.Len">func (IntSlice) <span>Len</span>  </h3> <pre data-language="go">func (x IntSlice) Len() int</pre> <h3 id="IntSlice.Less">func (IntSlice) <span>Less</span>  </h3> <pre data-language="go">func (x IntSlice) Less(i, j int) bool</pre> <h3 id="IntSlice.Search">func (IntSlice) <span>Search</span>  </h3> <pre data-language="go">func (p IntSlice) Search(x int) int</pre> <p>Search returns the result of applying <a href="#SearchInts">SearchInts</a> to the receiver and x. </p>
<h3 id="IntSlice.Sort">func (IntSlice) <span>Sort</span>  </h3> <pre data-language="go">func (x IntSlice) Sort()</pre> <p>Sort is a convenience method: x.Sort() calls Sort(x). </p>
<h3 id="IntSlice.Swap">func (IntSlice) <span>Swap</span>  </h3> <pre data-language="go">func (x IntSlice) Swap(i, j int)</pre> <h2 id="Interface">type <span>Interface</span>  </h2> <p>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. </p>
<pre data-language="go">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 &lt; 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)
}</pre> <h3 id="Reverse">func <span>Reverse</span>  <span title="Added in Go 1.1">1.1</span> </h3> <pre data-language="go">func Reverse(data Interface) Interface</pre> <p>Reverse returns the reverse order for data. </p>   <h4 id="example_Reverse"> <span class="text">Example</span>
</h4> <p>Code:</p> <pre class="code" data-language="go">s := []int{5, 2, 6, 3, 1, 4} // unsorted
sort.Sort(sort.Reverse(sort.IntSlice(s)))
fmt.Println(s)
</pre> <p>Output:</p> <pre class="output" data-language="go">[6 5 4 3 2 1]
</pre>   <h2 id="StringSlice">type <span>StringSlice</span>  </h2> <p>StringSlice attaches the methods of Interface to []string, sorting in increasing order. </p>
<pre data-language="go">type StringSlice []string</pre> <h3 id="StringSlice.Len">func (StringSlice) <span>Len</span>  </h3> <pre data-language="go">func (x StringSlice) Len() int</pre> <h3 id="StringSlice.Less">func (StringSlice) <span>Less</span>  </h3> <pre data-language="go">func (x StringSlice) Less(i, j int) bool</pre> <h3 id="StringSlice.Search">func (StringSlice) <span>Search</span>  </h3> <pre data-language="go">func (p StringSlice) Search(x string) int</pre> <p>Search returns the result of applying <a href="#SearchStrings">SearchStrings</a> to the receiver and x. </p>
<h3 id="StringSlice.Sort">func (StringSlice) <span>Sort</span>  </h3> <pre data-language="go">func (x StringSlice) Sort()</pre> <p>Sort is a convenience method: x.Sort() calls Sort(x). </p>
<h3 id="StringSlice.Swap">func (StringSlice) <span>Swap</span>  </h3> <pre data-language="go">func (x StringSlice) Swap(i, j int)</pre><div class="_attribution">
  <p class="_attribution-p">
    &copy; Google, Inc.<br>Licensed under the Creative Commons Attribution License 3.0.<br>
    <a href="http://golang.org/pkg/sort/" class="_attribution-link">http://golang.org/pkg/sort/</a>
  </p>
</div>