Sorting in Go from JavaScript

In computer science, sorting means taking a collection of items, and rearranging them so they are in a specified order, for example sorting a list of strings alphabetically, numbers from smallest to largest, or sorting structs by one of their fields. You can use this for things like making the inner workings of your algorithms more efficiently, or displaying data in a certain order (ex listing search results from newest to oldest).

For sorting in Go, the standard library provides the sort package to efficiently implement sorting for your data, and it makes cool use of Go interfaces to define the rules to sorting data. And it'll be familiar if you've used JavaScript's Array.prototype.sort method!

💬 Sorting strings

Let's start off with a slice of strings we want to sort in alphabetical order:

var languages = []string{"Go", "C", "Ruby", "JavaScript", "XML"}

In JavaScript, sorting them would look something like this:

let languages = ["Go", "C", "Ruby", "JavaScript", "XML"];

languages.sort();
console.log(languages); // ["C", "Go", "JavaScript", "Ruby", "XML"]

Since languages is an array, we can use Array.prototype.sort, to put them in order.

Since unlike JS arrays, Go slices don't have methods out of the box, instead of using an array sort method, we import the sort package and use its Sort function to rearrange our slices. Let's give it a try! Put this code in a file called sort-strings.go

package main

import (
    "fmt"
    "sort"
)

func main() {
    languages := []string{"Go", "C", "Ruby", "JavaScript", "XML"}
    sort.Sort(languages)

    fmt.Println(languages)
}

Then if you run go run sort-strings.go, you should get:

./sort-strings.go:10:14: cannot use languages (type []string) as type sort.Interface in argument to sort.Sort:
    []string does not implement sort.Interface (missing Len method)

A compiler error? The reason why that is, is because sort.Sort doesn't automatically take in a slice type. Its function signature actually looks like this:

func Sort(data Interface)

sort.Interface (with a big I) is a Go interface that represents a collection of data that can be sorted, like a list of strings, numbers, or even structs. And since sorting slices of strings and ints is common, the sort package gives you some built-in types that make slices of strings or ints compatible with sort.Sort. Try this out!

  func main() {
      languages := []string{"Go", "C", "Ruby", "JavaScript", "XML"}
-     sort.Sort(languages)
+     sort.Sort(sort.StringSlice(languages))

      fmt.Println(languages)
  }

sort.StringSlice is a slice of strings, but it has the methods needed to implement sort.Interface. So by converting a []string to a StringSlice, it can be sorted with sort.Sort! And now if you do go run sort-strings.go, you should see the list of programming languages in alphabetical order!

Why do we need a special interface, though, to be able to sort data, instead of Go just having sort.Sort take in slices? The reason why is because if we pass in a collection of items, Go needs a way of knowing what order the items go in. And to write those rules to sorting your slice, you implement the sort.Interface's methods. As you will see, Interface gives us flexibility to define the order of items whatever way you like!

🎨 Making a custom sort type

Let's say our languages slice included "fish" (a shell scripting language). If you're sorting that slice of programming tools in alphabetical order, it would make sense for the sorted slice to look like this:

[C, fish, Go, JavaScript, Ruby, XML]

But instead, "fish" goes last, even after XML! With sort.StringSlice, and same for sorting a list of strings in JS with Array.prototype.sort, the default sorting behavior is lexicographic order, not alphabetical order. And in lexicographic order, lowercase letters like the f in fish come after uppercase letters like the X in XML. If we want to sort by letter of the alphabet in a case-insensitive way, we need to implement some custom behavior. What would that look like?

To make custom sorting rules, we need to think about what sorting does. We're not going to look into the details of the different sorting algorithms like quicksort, mergesort, and bubblesort in this tutorial, but learning them is important in coding. The important thing you need to know about sorting algorithms for writing custom sorting rules in Go and JS, though, is that they need to:

1. Look at items in the collection
2. Compare them to see which ones should go first
3. Put the items in order based on those comparisons

In JavaScript, you would pass a custom function in to tell sort how to do comparisons between pairs of items in the array, like this:

languages.sort((langA, langB) => {
  langA = langA.toLowerCase();
  langB = langB.toLowerCase();
  if (langA < langB) {
    return -1; // return -1 if langA should go before langB in the array
  } else if (langB > langA) {
    return 1;  // return 1 if langB should go before langA in the array
  }
  return 0;    // return 0 if they can go in either order
})

Because we used toLowerCase before comparing languages, the language fish in all-lowercase does go before the capitalized Go, JavaScript, Ruby, and XML, but after C!

Now if we look at the Go sort.Interface, we'll see the methods we need to implement are pretty similar:

type Interface interface {
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}

So to make a type that can be sorted, we need to implement the sort.Interface so it can:

1. Tell Go's sort package the collection's Length
2. Take any two items in the collection (items i and j), and Swap them
3. Look at any two items in the collection and see which one should go first when the collection is sorted, with Less

Let's start by implementing Len and Swap.

type alphabeticalStrings []string

func (a alphabeticalStrings) Len() int { return len(a) }

func (a alphabeticalStrings) Swap(i, j int) {
    placeholder := a[j]
    a[j] = a[i]
    a[i] = placeholder
}

First, we define a type, alphabeticalStrings, on top of a string slice. By defining our own type in Go, we can write methods for it.

For Len, we just use Go's built-in len function to get how long our slice is, and for Swap, we swap two items in the slice. So far so good. Now let's implement Less. Import the strings package, and add in this function:

func (a alphabeticalStrings) Less(i, j int) bool {
    return strings.ToLower(a[i]) < strings.ToLower(a[j])
}

Notice something about the Less method? It looks an awful lot like that comparison method we made for Array.prototype.sort, except it returns a bool instead of an int and takes in slice indices instead of items!

Now, let's try it out! Edit the main function like this:

  func main() {
      languages := []string{"Go", "C", "fish", "Ruby", "JavaScript", "XML"}
-     sort.Sort(sort.StringSlice(languages))
+     sort.Sort(alphabeticalStrings(languages))

      fmt.Println(languages)
  }

And if you run go run sort-strings.go, now you should see the list sorted as expected!

[C, fish, Go, JavaScript, Ruby, XML]

You know what's cool about Go's sort.Interface? Both the alphabeticalStrings type we wrote and the StringSlice type the Go Team wrote are built on top of a plain old []string and can both be passed into sort.Sort. We can pick which order we want the strings in by picking which type we convert our slice of strings to!

😎 Simplify our sorting with sort.Slice!

One difference between the JS and Go versions of sort, was that to sort a Go slice, in addition to a comparison function, we needed to write those Len and Swap methods. And for any slice type, Len and Swap pretty much will always look the same. So to define a new sorting order, it feels kinda cumbersome to have to implement all three methods.

The reason for three methods is, the data structure you're implementing sort.Interface for doesn't necessarily have to be an array or slice. I've only used the sort package on slices, but you could implement a sort.Interface with some other type, like a linked list.

But for slices, where we're always using the same logic for Len and Swap, what if we only needed to implement Less, just like in JavaScript? The sort package has just the method to do that, sort.Slice!

func Slice(
    slice interface{},
    less func(i, j int) bool,
)

We pass in our slice of data that we want to sort as the first argument, and a function to compare the slice's item with as the second argument. Now we can sort our data without even making a new type! Let's try refactoring our main function one more time to try that out:

  func main() {
      languages := []string{"Go", "C", "fish", "Ruby", "JavaScript", "XML"}
-     sort.Sort(alphabeticalStrings(languages))
+     sort.Slice(languages, func(i, j int) bool {
+         return strings.ToLower(languages[i]) < strings.ToLower(languages[j])
+     })

      fmt.Println(languages)
  }

All right! We've got our sorted slice!

Something else cool about the sort package, in addition to us being able to pick which order we're sorting by, notice that in sort.Sort and sort.Slice, we didn't need to know which sorting algorithm we're using. sort.Sort handles implementing the algorithm, and all the function needs to know from us is how to compare items, how to swap them, and how many items we have. That's interfaces in action!

By the way, being familiar with how sorting algorithms work is still definitely worthwhile since you'll know the clever techniques to having your computer do less work to arrange data, and since sorting is used everywhere. So if you want to learn how they work and what sort.Sort is doing behind the scenes with those functions we wrote, Below is some materials on the algorithms themselves.

• Free Code Camp - Sorting Algorithms Explained
• Toptal - Sorting Algorithm Animations
• Implementing Sorting Algorithms in JavaScript