Go 標準のソート・アルゴリズム

今回は

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

から着想を得て Go 標準の sort パッケージについて簡単に紹介する。なお今回の記事は，以前 LT 用に書いたスライド「配列とスライスとソート」からの抜粋となっている。よろしければスライドの方もご笑覧あれ。

まずはコード

Go 標準の sort パッケージでは任意の slice ソートについて以下のように記述できる。

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
}

このコードの実行結果は以下の通り。

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

sort パッケージでは slice に対して2種類のソート関数を用意していて

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

このうち sort.SliceStable() 関数のほうを安定ソート（挿入ソート）として記述がされている。

Sort パッケージで使われているアルゴリズム

Sort パッケージの sort.Slice() 関数では以下のように複数のアルゴリズムを使い分けている。

1. 基本はクイックソート
2. 要素数が12以下ならシェルソート（gap 6）へ
3. 要素数が6以下なら挿入ソートへ
4. クイックソートの再帰レベルが一定を超えたらヒープソートへ（イントロソート）
   • $depth = \lceil \mathrm{lb}(n+1)\rceil\times 2$

ちなみにアルゴリズム毎の計算量は以下のとおりである。

名前	最良	最悪	平均
クイックソート	$\mathrm{O}(n \log n)$	$\mathrm{O}(n^2)$	$\mathrm{O}(n \log n)$
ヒープソート	$\mathrm{O}(n \log n)$	$\mathrm{O}(n \log n)$	$\mathrm{O}(n \log n)$
シェルソート	$\mathrm{O}(n \log^2 n)$	$\mathrm{O}(n^2)$	—
挿入ソート	$\mathrm{O}(n)$	$\mathrm{O}(n^2)$	$\mathrm{O}(n^2)$

参考

Go 1.19 で採用された Pattern-defeating Quicksort を紹介するスライドです。