Sorting in Go

In order to sort a slice we can use the sort package from the standard library, which provides functions to sort slices in ascending order (default), descending order or user-defined order.

Syntax:

The main sorting functions in the sort package are:

sort.Ints(slice)
sort.Strings(slice)
sort.Slice(slice, func(i, j int) bool { ... })

Let's see some examples below. Sorting a slice of integers in ascending order

numbers := []int{11, 3, 7, 5, 2}

sort.Ints(numbers) // numbers becomes [2, 3, 5, 7, 11]

Sorting a slice of integers in descending order

numbers := []int{11, 3, 7, 5, 2}

sort.Sort(sort.Reverse(sort.IntSlice(numbers)))

Sorting a slice of strings in descending order

names := []string{"Mircea", "Andy", "Xavier", "Michael", "Christina"}

sort.Sort(sort.Reverse(sort.StringSlice(names)))  // names becomes [Xavier Mircea Michael Christina Andy]

Sort with custom function (comparator):

sort.Slice() supports a less function that we can use to specify how we want to sort:

func less(i, j int) bool {
    return numbers[i] < numbers[j]
}

This can be written as an anonymous function (nameless function we can easily pass to sort.Slice()) as follows:

func(i, j int) bool {
    return numbers[i] < numbers[j]
}

In Go, the less function receives indices i and j and accesses the slice elements to compare them:

func(i, j int) bool {
    return slice[i] < slice[j]
}

When the sort.Slice() function compares two elements, it calls the less function with their indices, and sorts the elements according to the returned value:

• If the result is true then the element at index i is sorted before the element at index j.
• If the result is false then the element at index j is sorted before the element at index i.

All we need to do is pass the anonymous function inside sort.Slice():

numbers := []int{3, 23, 12}

sort.Slice(numbers, func(i, j int) bool { return numbers[i] < numbers[j] }) // numbers becomes [3 12 23]

To demonstrate a basic example, let's assume the requirement for ordering a specific list is the length of the strings in the list, shortest to longest. We will be using the len() function of each string to compare them.

words := []string{"banana", "pie", "Washington", "book"}

sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) }) // words becomes [pie book banana Washington]

Example: sorting a slice of pairs

Let's say we want to sort a slice, where each element is another slice consisting of two numbers.

pairs := [][]int{{1, 5}, {12, 5}, {10, 1}, {1, 3}}

sort.Slice(pairs, func(i, j int) bool {
    // in case the first values of each pair are equal,
    // compare them using their second values
    if pairs[i][0] == pairs[j][0] {
        return pairs[i][1] < pairs[j][1]
    }
    return pairs[i][0] < pairs[j][0]
})
// pairs becomes [[1 3] [1 5] [10 1] [12 5]]

Time Complexity:

Sorting a slice via sort.Slice() takes O(n * log n * C) time, where C is the time taken to compare two elements from the slice.

It takes O(1) (constant time) to compare two numbers, therefore sorting a slice of numbers takes O(n log n).

However, it takes O(L) to compare two strings, therefore sorting a slice of strings takes O(n * log n * L), where L is the average length of the strings.

Space Complexity:

The sort.Slice() function sorts the elements of a slice in place (transforms the slice directly, using no auxiliary data structure), so the extra space used for this is small: no auxiliary slice is created, only O(log n) of recursion stack.

Assignment
Follow the Coding Tutorial and let's sort some slices.

Hint
Look at the examples above if you get stuck.