Sorting in Go: sort.Ints and sort.Slice

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 an array of integers in ascending order

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

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

Sorting an array of integers in descending order

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

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

Sorting an array of Strings in descending order

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

sort.Sort(sort.Reverse(sort.StringSlice(names)))  // --> ['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] }) // --> 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]) }) // --> ['pie', 'book', 'banana', 'Washington']

Example: sorting array of pairs

Let's say we want to sort an array, where each element is another array 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 --> [[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 array.

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

However, it takes O(L) to compare two strings, therefore sorting an array 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 O(1).

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

Hint
Look at the examples above if you get stuck.