A Go slice is an abstraction built on top of Go’s array type. Usually we work with slices, and not with arrays directly – here’s why. But arrays do come in handy at times–as map keys, for example – we can’t use slices as map keys–and sometimes we need to sort them.
Let’s sort a slice of three items, then try to sort an [3]item array that has identical items in it.
(We could use sort.Ints on our slice, rather than creating our items type based on []int, but we cannot call sort.Ints on our [3]int array.) Here’s why
We’ll create an items type based on []item, and another items type based on [3]item, and implement sort.Interface on each:
1package main
2
3type item struct {
4 id int
5}
6
7type items []item
8
9func (item items) Len() int {
10 return len(item)
11}
12func (item items) Swap(i, j int) {
13 item[i], item[j] = item[j], item[i]
14}
15func (item items) Less(i, j int) bool {
16 return item[i].id < item[j].id
17}
18
19func main() {
20
21 sl := items{
22 {
23 id: 3,
24 },
25 {
26 id: 1,
27 },
28 {
29 id: 2,
30 },
31 }
32
33 fmt.Println(sl)
34
35 sort.Sort(sl)
36
37 fmt.Println(sl)
38}1> [{3} {1} {2}]
2> [{1} {2} {3}]Ok, that works. Now let’s try to do the same thing with an [3]item array:
1package main
2
3import (
4 "fmt"
5 "sort"
6)
7
8type item struct {
9 id int
10}
11
12type items [3]item
13
14func (item items) Len() int {
15 return len(item)
16}
17func (item items) Swap(i, j int) {
18 item[i], item[j] = item[j], item[i]
19}
20func (item items) Less(i, j int) bool {
21 return item[i].id < item[j].id
22}
23
24func main() {
25
26 sl := items{
27 {
28 id: 3,
29 },
30 {
31 id: 1,
32 },
33 {
34 id: 2,
35 },
36 }
37
38 fmt.Println(sl)
39
40 sort.Sort(sl)
41
42 fmt.Println(sl)
43}1> [{3} {1} {2}]
2> [{3} {1} {2}]That doesn’t work, and here’s why.
Let’s take a look at Go’s (1.21.5) sort.Sort function. It is the heart of Go’s sort package.
1func Sort(data Interface) {
2 n := data.Len()
3 if n <= 1 {
4 return
5 }
6 limit := bits.Len(uint(n))
7 pdqsort(data, 0, n, limit)
8}pdqsort chooses a sorting algorithm based on input. All the sort package’s algorithms handle their input (data) similarly. Let’s look at one of them, heapSort
1func heapSort(data Interface, a, b int) {
2first := a
3lo := 0
4hi := b - a
5
6 // Build heap with greatest element at top.
7 for i := (hi - 1) / 2; i >= 0; i-- {
8 siftDown(data, i, hi, first)
9 }
10
11 // Pop elements, largest first, into end of data.
12 for i := hi - 1; i >= 0; i-- {
13 data.Swap(first, first+i)
14 siftDown(data, lo, i, first)
15 }
16
17}Go is a pass-by-value language, which means, in the heapSort function, the data value inside the function is a copy of the value we pass in. The copy of the data param is modified, but the caller’s data is not.
By contrast, a Go slice is a descriptor that refers to an underlying array. It has three fields: a pointer to an element of the underlying array, the length of the slice segment, and the slice’s capacity. See here
Where we pass a slice to heapSort, data.Swap operates on the underlying array the slice points to. That’s the key part to understand about slices: where we make a copy of a slice, the slice copy points to the same underlying array as the original slice.
See Go slices are not pointers!.
To sort a Go array using Go’s sort package, create a type based on your array, and implement sort.Interface using your type’s pointer receiver:
1package main
2
3import (
4 "fmt"
5 "sort"
6)
7
8type item struct {
9 id int
10}
11
12type items [3]item
13
14// note item's pointer receiver here
15func (item *items) Len() int {
16 return len(item)
17}
18func (item *items) Swap(i, j int) {
19 item[i], item[j] = item[j], item[i]
20}
21func (item *items) Less(i, j int) bool {
22 return item[i].id < item[j].id
23}
24
25func main() {
26 sl := items{
27 {
28 id: 3,
29 },
30 {
31 id: 1,
32 },
33 {
34 id: 2,
35 },
36 }
37
38 fmt.Println(sl)
39
40 sort.Sort(&sl)
41
42 fmt.Println(sl)
43}1> [{3} {1} {2}]
2> [{1} {2} {3}]Go pointers, like all other function params, are passed by value. What this means is that the original pointer, and its copy inside the function, both point to the same piece of memory.