The Standard Sorting Algorithms in Go

In this post, inspired by

https://zenn.dev/satoru_takeuchi/articles/d66b8b69e0218d9f137e

I will briefly introduce the standard Go sort package. This article is an excerpt from a slide deck I previously wrote for an LT titled "Arrays, Slices, and Sorting". Please feel free to take a look at the slides as well.

First, the Code

In the standard Go sort package, you can write an arbitrary slice sort as follows:

package main

import (
    "fmt"
    "sort"
)

func main() {
    ds := []float64{0.055, 0.815, 1.0, 0.107}
    fmt.Println(ds) //before
    sort.Slice(ds, func(i, j int) bool {
        return ds[i] < ds[j]
    })
    fmt.Println(ds) //after
}

The execution result of this code is as follows:

[0.055 0.815 1 0.107]
[0.055 0.107 0.815 1]

The sort package provides two types of sorting functions for slices:

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

Among these, the sort.SliceStable() function is implemented as a stable sort (insertion sort).

Algorithms Used in the sort Package

The sort.Slice() function in the sort package uses multiple algorithms depending on the situation:

1. Primarily Quicksort
2. Switches to Shell sort (gap 6) if the number of elements is 12 or fewer
3. Switches to Insertion sort if the number of elements is 6 or fewer
4. Switches to Heapsort if the recursion level of Quicksort exceeds a certain limit (Introsort)
   • $depth = \lceil \mathrm{lb}(n+1)\rceil\times 2$

For reference, the computational complexity for each algorithm is as follows:

Name	Best	Worst	Average
Quicksort	$\mathrm{O}(n \log n)$	$\mathrm{O}(n^2)$	$\mathrm{O}(n \log n)$
Heapsort	$\mathrm{O}(n \log n)$	$\mathrm{O}(n \log n)$	$\mathrm{O}(n \log n)$
Shell sort	$\mathrm{O}(n \log^2 n)$	$\mathrm{O}(n^2)$	—
Insertion sort	$\mathrm{O}(n)$	$\mathrm{O}(n^2)$	$\mathrm{O}(n^2)$

References

This slide deck introduces the Pattern-defeating Quicksort adopted in Go 1.19.