Sorting in Go – Don’t Reinvent This Wheel

Sorting is a common task in programming, and for that reason, most languages have a default sorting algorithm in their standard library. Go is one such language. Go has gone about providing sorting functionality in one of the most elegant ways possible, via an interface.

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) }
Code language: Go (go)

Any type that satisfies this interface can be sorted using the standard library’s sort.Sort() function. There is rarely a reason to sort any other way because the sort function is O(n log(n)) in the worst case. You can take a look at the various algorithms that are used, depending on the data to be sorted, here.

Sorry to interrupt! I just wanted to mention that you should check out my new free Go course. It’s designed to teach you all the fundamentals of my favorite coding language.

Sorting a Slice

The first thing to do, no matter what we are sorting is to create a custom type. A custom type will allow us to implement the Len(), Less() and Swap() methods on it.

type mySlice []int
Code language: Go (go)

Then we implement the methods to fulfill the sort.Interface interface:

func (ms mySlice) Len() int { return len(ms) } func (ms mySlice) Less(i, j int) bool { return ms[i] < ms[j] } func (ms mySlice) Swap(i, j int) { ms[i], ms[j] = ms[j], ms[i] }
Code language: Go (go)

Let’s test it out:

package main import ( "fmt" "math/rand" "sort" ) type mySlice []int func (ms mySlice) Len() int { return len(ms) } func (ms mySlice) Less(i, j int) bool { return ms[i] < ms[j] } func (ms mySlice) Swap(i, j int) { ms[i], ms[j] = ms[j], ms[i] } func main() { ms := mySlice{} for i := 0; i < 10; i++ { ms = append(ms, rand.Intn(100)) } fmt.Println("pre-sort:", ms) sort.Sort(ms) fmt.Println("post-sort:", ms) }
Code language: Go (go)

prints:

pre-sort: [81 87 47 59 81 18 25 40 56 0] post-sort: [0 18 25 40 47 56 59 81 81 87]
Code language: CSS (css)

Changing It Up

Rather than changing the way we call the sort function, if we want different behavior we just change the way we implement the interface. For example, if we want to sort greatest to least we just change the Less() function:

func (ms mySlice) Less(i, j int) bool { return ms[i] > ms[j] }
Code language: Go (go)

which prints:

pre-sort: [81 87 47 59 81 18 25 40 56 0] post-sort: [87 81 81 59 56 47 40 25 18 0]
Code language: CSS (css)

Other Types

Sorting integers is pretty boring. Besides, if we are just going to sort integers we can use the pre-defined IntSlice type instead of coding it all again ourselves. Let’s sort a slice of structs:

type mtgCard struct { manaCost int name string } type mtgCards []mtgCard
Code language: Go (go)

Now we implement the sorting:

func (mCards mtgCards) Len() int { return len(mCards) } func (mCards mtgCards) Less(i, j int) bool { if mCards[i].manaCost < mCards[j].manaCost { return true } else if mCards[i].manaCost == mCards[j].manaCost { return mCards[i].name < mCards[j].name } return false } func (mCards mtgCards) Swap(i, j int) { mCards[i], mCards[j] = mCards[j], mCards[i] }
Code language: Go (go)

The Less() function we made will sort by manacost unless their is a tie, in which case it will sort by name. Let’s test it out:

func main() { mCards := mtgCards{ { manaCost: 7, name: "ajani", }, { manaCost: 2, name: "liliana", }, { manaCost: 2, name: "chandra", }, { manaCost: 4, name: "garruk", }, { manaCost: 4, name: "jace", }, { manaCost: 5, name: "bolas", }, } fmt.Println("pre-sort:", mCards) sort.Sort(mCards) fmt.Println("post-sort:", mCards) }
Code language: Go (go)

prints:

pre-sort: [{7 ajani} {2 liliana} {2 chandra} {4 garruk} {4 jace} {5 bolas}] post-sort: [{2 chandra} {2 liliana} {4 garruk} {4 jace} {5 bolas} {7 ajani}]
Code language: CSS (css)

Don’t Reinvent It

The standard library’s sorting methods are powerful, don’t code them yourself unless you have a very extreme use case. Take a look at some of the other functionality provided by the sort package as well if you have time. Searching, stable sorting, and checking if a type is sorted are some pretty awesome features.

Have questions or feedback?

Follow and hit me up on Twitter @q_vault if you have any questions or comments. If I’ve made a mistake in the article, please let me know so I can get it corrected!

Related Reading

Leave a Comment