Go 標準パッケージの sort を読んでみる

この記事は IIJ 2018 TECH アドベントカレンダー 12/13 の記事です。

どうも、IIJ で今年の 10 月から Go を書く仕事をしている、こないだ PayPay で surface 買ったら 10万 返ってきて、わくわくで開封したら初期不良引いた yota(社内のアカウント名)/@tennashi といいます
個人的なメモ以外を Qiita に書くのは初めてです

社内チャットの golang チャンネルで sort パッケージの話題が出て、interface の使い方の例として面白そうだなぁと感じたため、今回は sort パッケージの中身を読んでいきたいと思います
本当は Go and/or clean architecture ネタでも書こうと思ったんですが、もろ被ってしまったのでネタを変更してお送りしますｗ
(この記事を書いた方は私の左隣の席で同じコードを書いている先輩なので被ることは必然であった...!!!)

まずは sort パッケージで定義された関数/型を整理してみる

コードを読み始める前に sort パッケージのドキュメント から読むべき部分にあたりを付ける

特定の slice 型に対する処理

[]float64

• Float64s(a []float64)
• Float64sAreSorted(a []float64) bool
• SearchFloat64s(a []float64, x float64)

[]int

• Ints(a []int)
• IntsAreSorted(a []int) bool
• SearchInts(a []int, x int)

[]string

• Strings(a []string)
• StringsAreSorted(a []string)
• SearchStrings(a []string, x string)

汎用的な slice に対する処理

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

汎用的な型に対する処理

• Stable(data Interface)
• Sort(data Interface)
• IsSorted(data Interface) bool
• Search(n int, f func(int) bool) int
• Reverse(data Interface) Interface

sort パッケージで定義されている型/インターフェイス及びそのメソッド

Float64Slice

• Len() int
• Less(i, j int) bool
• Search(x float64) int
• Sort()
• Swap(i, j int)

IntSlice

• Len() int
• Less(i, j int) bool
• Search(x int) int
• Sort()
• Swap(i, j int)

StringSlice

• Len() int
• Less(i, j int) bool
• Search(x string) int
• Sort()
• Swap(i, j int)

Interface

• Len() int
• Less(i, j int) boot
• Swap(i, j int)

ここまででわかるのは

• Sort, IsSorted, Search が全ての型で定義されている
• 恐らく具体的な型 []float64 []int []string に対する処理は汎用的な型に対する処理に帰着されているので、Interface 型についての処理を読めばよい
• それらの Sort, IsSorted, Search 処理は Interface 型の interface である Len Less Swap を用いて定義されており、[]float64 等については Interface 型を満たす Float64Slice IntSlice StringSlice を経由して書かれているはず
• 汎用的な slice 型に対する処理は、引数の雰囲気が違うので上記に当てはまらなそう

というわけでがんばって読んでいきたいと思います

[]int 等の処理が IntSlice 等を経由して、Interface 型に対する Sort IsSorted Search に帰着されている部分を読む

以下 []int []float64 []string の処理は同様である可能性が高いため、代表して []int を中心に読んでいく

Ints(a []int) を読む

このあたりは簡単なのでさらっと

src/sort/sort.go

// Ints sorts a slice of ints in increasing order.
func Ints(a []int) { Sort(IntSlice(a)) }

はい、Sort(data Interface) を Sort(IntSlice(a)) という形で呼び出していますね
IntSlice 型は Interface 型を満たしているのでこれでよいですね

ついでに (p IntSlice) Sort() も同じなので読んでみます

src/sort/sort.go

// Sort is a convenience method.
func (p IntSlice) Sort() { Sort(p) }

はい、というわけで Ints(a []int) も (p IntSlice) Sort() と同じなので、結局 Sort(data Interface) を読めばよいということでよさそうですね

Sort(data Interface) を読む

src/sort/sort.go

// Sort sorts data.
// It makes one call to data.Len to determine n, and O(n*log(n)) calls to
// data.Less and data.Swap. The sort is not guaranteed to be stable.
func Sort(data Interface) {
    n := data.Len()
    quickSort(data, 0, n, maxDepth(n))
}

quickSort ですね、知らんけど。

はい、続きを書く前に一般的な quick sort について調べます

Wikipedia 先生によると

1. 適当な数（ピボットという）を選択する （この場合はデータの総数の中央値が望ましい）
2. ピボットより小さい数を前方、大きい数を後方に移動させる （分割）
3. 二分割された各々のデータを、それぞれソートする

実際にこれを実現するためのアルゴリズムは色々考えられるが、一例を挙げると以下のようなものがある。

1. ピボットとして一つ選びそれをPとする。
2. 左から順に値を調べ、P以上のものを見つけたらその位置をiとする。
3. 右から順に値を調べ、P以下のものを見つけたらその位置をjとする。
4. iがjより左にあるのならばその二つの位置を入れ替え、2に戻る。ただし、次の2での探索はiの一つ右、次の3での探索はjの一つ左から行う。
5. 2に戻らなかった場合、iの左側を境界に分割を行って2つの領域に分け、そのそれぞれに対して再帰的に1からの手順を行う。要素数が1以下の領域ができた場合、その領域は確定とする。

注：このアルゴリズムでは、領域の左端の値が領域内で最小かつ同じ値が他の位置に無い場合、ピボットとしてその値を選ぶと同じ領域を再帰的に呼び出す無限ループとなってしまう。

ピボットに決めた数より大きい数の配列と小さい数の配列に分割して各々に対して再帰的にアルゴリズムを適用していくという感じのよう

これを念頭に置いて実装を読む

src/sort/sort.go

func quickSort(data Interface, a, b, maxDepth int) {
    for b-a > 12 { // Use ShellSort for slices <= 12 elements
        if maxDepth == 0 {
            heapSort(data, a, b)
            return
        }
        maxDepth--
        mlo, mhi := doPivot(data, a, b)
        // Avoiding recursion on the larger subproblem guarantees
        // a stack depth of at most lg(b-a).
        if mlo-a < b-mhi {
            quickSort(data, a, mlo, maxDepth)
            a = mhi // i.e., quickSort(data, mhi, b)
        } else {
            quickSort(data, mhi, b, maxDepth)
            b = mlo // i.e., quickSort(data, a, mlo)
        }
    }
    if b-a > 1 {
        // Do ShellSort pass with gap 6
        // It could be written in this simplified form cause b-a <= 12
        for i := a + 6; i < b; i++ {
            if data.Less(i, i-6) {
                data.Swap(i, i-6)
            }
        }
        insertionSort(data, a, b)
    }
}

data は元の配列、a b は quick sort する始点終点、maxDepth は再帰の深さを表しているようです
これを読むと条件に応じて使用するソートアルゴリズムを変更していることが分かります

• b - a > 12 であり maxDepth 回までは quick sort
  • maxDepth == 0 になったら heap sort
• 1 < b - a <= 12 のときは gap 6 の shell sort
  • 完了したら insertion sort
• b - a == 1 のときは要素数 1 なのでソート済み

はい、というわけで色々なソートアルゴリズムを見ていきます

heap sort

ヒープソート

ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである[2]（ヒープ領域とは無関係であることに注意する）。

アルゴリズムは、以下のように2つの段階から構成される。

1. 未整列のリストから要素を取り出し、順にヒープに追加する。すべての要素を追加するまで繰り返し。
2. ルート（最大値または最小値)を取り出し、整列済みリストに追加する。すべての要素を取り出すまで繰り返し。

で、二分ヒープ木は次の条件を満たす二分木のこと

• 要素間の順序関係に従った比較によって、各々のノードはそのノードの子よりも大きいか等しくなるように配置される（heap property）

• 木は完全にバランスの取れた二分木（すべての葉は同じ高さにある）になるか、木のもっとも高い方がすべて埋まっていないならば、ノードは左から右へ順に埋まっていく（shape property）

いい感じの木構造を用意して、そこから要素を取り出していくとソート済み配列が得られるやつ

insertion sort

挿入ソート

まず0番目と1番目の要素を比較し、順番が逆であれば入れ換える。次に、2番目の要素が1番目までの要素より小さい場合、正しい順に並ぶように「挿入」する（配列の場合、前の要素を後ろに一つずつずらす）。この操作で、2番目までのデータが整列済みとなる（ただし、さらにデータが挿入される可能性があるので確定ではない）。このあと、3番目以降の要素について、整列済みデータとの比較と適切な位置への挿入を繰り返す。

ソート対象がソート済み部分のどこに入るのかを頭から頑張って探していくやつ

shell sort

シェルソート

基本的な部分は、挿入ソートと同じである。挿入ソートは「ほとんど整列されたデータに対しては高速」という特長があるものの、「隣り合った要素同士しか交換しない」ため、あまり整列されていないデータに対しては低速であった。

そのため、適当な間隔をあけた飛び飛びのデータ列に対してあらかじめソートしておき、挿入ソートを適用すれば高速になると考えられる。この考え方を適用したのがシェルソートである。

1. 適当な間隔 h を決める
2. 間隔 h をあけて取り出したデータ列に挿入ソートを適用する
3. 間隔 h を狭めて、2.を適用する操作を繰り返す
4. h=1 になったら、最後に挿入ソートを適用して終了

insertion sort の分割統治版みたいなやつ

条件分岐の意図を考えていきます

注: 私の想像で書いているため、正確性は保証しません。また、理由をご存じの方がいらっしゃいましたら、コメントしていただけると幸いです。

maxDepth 回までは quick sort、maxDepth == 0 になったら heap sort

quick sort は再帰的に定義されているため、メモリを食い潰さないよう再帰の深さをある程度制限する必要があります
そのため maxDepth 回の深さに制限しています

maxDepth == 0 の時に heap sort を使うのは heap sort も $O(n \log n)$ であるからと想像します

1 < b - a <= 12 のときは gap 6 の shell sort、完了したら insertion sort

前述の shell sort のアルゴリズムを見ると、最後に insertion sort をする部分は shell sort のアルゴリズムの一部であることが分かります
よって、この部分は単純に「1 < b - a <= 12 のときは shell sort する」と考えればよさそうです

なぜ要素数が 12 以下の場合は shell sort しているのだろうか

と、まあここまで考えたところで

イントロソート

イントロソート（英: introsort）は、David Musser が1997年に設計したソートアルゴリズムである。最初はクイックソートを行い、再帰のレベルがソートされた要素数（の対数）を超えるとヒープソートに切り替える。最悪でも O(n log n) であり、同時に典型的なデータに対するソートではクイックソートに匹敵する性能を示す。クイックソートもヒープソートも比較ソートであり、イントロソートも同様である。
(中略)
Musser によれば、クイックソートが最悪値を示すようなリストであっても、イントロソートではその1/1200の時間でソートを完了する。Musser は Robert Sedgewick が考案したキャッシュメモリの効果を考慮したソートアルゴリズムも検討した。それは、細かい部分について挿入ソートを1回最後に行うというものである。彼によると、イントロソートではキャッシュミス率は2倍になるが、両端キューを使った実装では劇的に性能を改善できるため、テンプレートライブラリに保持すべきだとしている（特に、キャッシュの保持されている間にソートを行わないこともあるため）。

適当にググっていたらこれが見つかり、なるほどー、これかーとなりました
quick sort の最悪計算時間は $O(n^2)$ であり、bubble sort と同じオーダ(つまり、比較的遅いアルゴリズムと同じくらいの計算時間)になってしまいます
世の中にはこれを利用しサーバに負荷をかける攻撃があるようです

それを避けるためのアルゴリズムが考案されており、そのうちの一つが intro sort のようです
なぜ要素数が 12 であるか、については不明ですが(ベンチマークの結果とかありそう)、sort パッケージでの quick sort の実装は intro sort に準ずるものであると考えられます

では一応 maxDepth の実装を見てみます

src/sort/sort.go

// maxDepth returns a threshold at which quicksort should switch
// to heapsort. It returns 2*ceil(lg(n+1)).
func maxDepth(n int) int {
    var depth int
    for i := n; i > 0; i >>= 1 {
        depth++
    }
    return depth * 2
}

// Sort sorts data.
// It makes one call to data.Len to determine n, and O(n*log(n)) calls to
// data.Less and data.Swap. The sort is not guaranteed to be stable.
func Sort(data Interface) {
    n := data.Len()
    quickSort(data, 0, n, maxDepth(n))
}

コメントに書いてある通り、$2 \lceil \log_2 (n + 1) \rceil$ を計算しています
>> は shift 関数なので i >>= 1 は "大体 i / 2" をしており、その繰り返し回数を depth に貯めていっていますね

まあ、微妙に wikipedia 先生の主張とはずれていますが、再帰の深さが制限されており、その回数以降は heap sort に以降する、という部分が重要なのであまり気にしないでおきます。恐らく最適化の賜物でしょう。

quick sort の中身を読む

src/sort/sort.go

func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
    m := int(uint(lo+hi) >> 1) // Written like this to avoid integer overflow.
    if hi-lo > 40 {
        // Tukey's ``Ninther,'' median of three medians of three.
        s := (hi - lo) / 8
        medianOfThree(data, lo, lo+s, lo+2*s)
        medianOfThree(data, m, m-s, m+s)
        medianOfThree(data, hi-1, hi-1-s, hi-1-2*s)
    }
    medianOfThree(data, lo, m, hi-1)

    // Invariants are:
    //  data[lo] = pivot (set up by ChoosePivot)
    //  data[lo < i < a] < pivot
    //  data[a <= i < b] <= pivot
    //  data[b <= i < c] unexamined
    //  data[c <= i < hi-1] > pivot
    //  data[hi-1] >= pivot
    pivot := lo
    a, c := lo+1, hi-1

    for ; a < c && data.Less(a, pivot); a++ {
    }
    b := a
    for {
        for ; b < c && !data.Less(pivot, b); b++ { // data[b] <= pivot
        }
        for ; b < c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot
        }
        if b >= c {
            break
        }
        // data[b] > pivot; data[c-1] <= pivot
        data.Swap(b, c-1)
        b++
        c--
    }
    // If hi-c<3 then there are duplicates (by property of median of nine).
    // Let be a bit more conservative, and set border to 5.
    protect := hi-c < 5
    if !protect && hi-c < (hi-lo)/4 {
        // Lets test some points for equality to pivot
        dups := 0
        if !data.Less(pivot, hi-1) { // data[hi-1] = pivot
            data.Swap(c, hi-1)
            c++
            dups++
        }
        if !data.Less(b-1, pivot) { // data[b-1] = pivot
            b--
            dups++
        }
        // m-lo = (hi-lo)/2 > 6
        // b-lo > (hi-lo)*3/4-1 > 8
        // ==> m < b ==> data[m] <= pivot
        if !data.Less(m, pivot) { // data[m] = pivot
            data.Swap(m, b-1)
            b--
            dups++
        }
        // if at least 2 points are equal to pivot, assume skewed distribution
        protect = dups > 1
    }
    if protect {
        // Protect against a lot of duplicates
        // Add invariant:
        //  data[a <= i < b] unexamined
        //  data[b <= i < c] = pivot
        for {
            for ; a < b && !data.Less(b-1, pivot); b-- { // data[b] == pivot
            }
            for ; a < b && data.Less(a, pivot); a++ { // data[a] < pivot
            }
            if a >= b {
                break
            }
            // data[a] == pivot; data[b-1] < pivot
            data.Swap(a, b-1)
            a++
            b--
        }
    }
    // Swap pivot into middle
    data.Swap(pivot, b-1)
    return b - 1, c
}

doPivot は pivot を決定し、data を pivot より以下部分、pivot と同じ値の部分、pivot より大きい部分に分割し、pivot と同じ部分の区間の両端を返す

ここではいくつかの部分に分解して読んでいく

• pivot を決定し、配列の頭に持ってくる

    m := int(uint(lo+hi) >> 1) // Written like this to avoid integer overflow.
    if hi-lo > 40 {
        // Tukey's ``Ninther,'' median of three medians of three.
        s := (hi - lo) / 8
        medianOfThree(data, lo, lo+s, lo+2*s)
        medianOfThree(data, m, m-s, m+s)
        medianOfThree(data, hi-1, hi-1-s, hi-1-2*s)
    }
    medianOfThree(data, lo, m, hi-1)

• 配列を pivot 以上と pivot 以下の部分と pivot より大きい部分に分割する

    // Invariants are:
    //  data[lo] = pivot (set up by ChoosePivot)
    //  data[lo < i < a] < pivot
    //  data[a <= i < b] <= pivot
    //  data[b <= i < c] unexamined
    //  data[c <= i < hi-1] > pivot
    //  data[hi-1] >= pivot
    pivot := lo
    a, c := lo+1, hi-1

    for ; a < c && data.Less(a, pivot); a++ {
    }
    b := a
    for {
        for ; b < c && !data.Less(pivot, b); b++ { // data[b] <= pivot
        }
        for ; b < c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot
        }
        if b >= c {
            break
        }
        // data[b] > pivot; data[c-1] <= pivot
        data.Swap(b, c-1)
        b++
        c--
    }

• hi - c が小さい場合 pivot と同じ値の区間の始点と終点を返す

    // If hi-c<3 then there are duplicates (by property of median of nine).
    // Let be a bit more conservative, and set border to 5.
    protect := hi-c < 5
    if !protect && hi-c < (hi-lo)/4 {
        // Lets test some points for equality to pivot
        dups := 0
        if !data.Less(pivot, hi-1) { // data[hi-1] = pivot
            data.Swap(c, hi-1)
            c++
            dups++
        }
        if !data.Less(b-1, pivot) { // data[b-1] = pivot
            b--
            dups++
        }
        // m-lo = (hi-lo)/2 > 6
        // b-lo > (hi-lo)*3/4-1 > 8
        // ==> m < b ==> data[m] <= pivot
        if !data.Less(m, pivot) { // data[m] = pivot
            data.Swap(m, b-1)
            b--
            dups++
        }
        // if at least 2 points are equal to pivot, assume skewed distribution
        protect = dups > 1
    }
    if protect {
        // Protect against a lot of duplicates
        // Add invariant:
        //  data[a <= i < b] unexamined
        //  data[b <= i < c] = pivot
        for {
            for ; a < b && !data.Less(b-1, pivot); b-- { // data[b] == pivot
            }
            for ; a < b && data.Less(a, pivot); a++ { // data[a] < pivot
            }
            if a >= b {
                break
            }
            // data[a] == pivot; data[b-1] < pivot
            data.Swap(a, b-1)
            a++
            b--
        }
    }
    // Swap pivot into middle
    data.Swap(pivot, b-1)
    return b - 1, c

pivot を決定し、配列の頭に持ってくる

まず、前提として、quick sort では分割の要素数が極端に差があればあるほど、sort の効率が悪くなります
例えば、pivot として配列の先頭を常に選択することとし、昇順で quick sort する場合は、降順でソート済みの配列を食わせる場合に最悪の計算時間がかかるはずです(ちゃんと確かめてないですが...)
つまり、理想としては、全体の中央値を使用するのがよいはずです
しかし、全体の中央値が判明している状況とは、ほぼソートが完了している状態のはずであるため、それっぽい値を上手くとる必要があります

ここでは配列の先頭、中央、最後尾の値を比較し、その3つの数の中央値を取ることで、それっぽい値としています
また要素数が多い場合は先頭近くで3つ、中央近くで3つ、最後尾近くで3つ、それぞれの中央値を選択し、その3つの中央値の中央値を取っています。

    m := int(uint(lo+hi) >> 1) // Written like this to avoid integer overflow.
    if hi-lo > 40 {
        // Tukey's ``Ninther,'' median of three medians of three.
        s := (hi - lo) / 8
        medianOfThree(data, lo, lo+s, lo+2*s)
        medianOfThree(data, m, m-s, m+s)
        medianOfThree(data, hi-1, hi-1-s, hi-1-2*s)
    }
    medianOfThree(data, lo, m, hi-1)

頭の m := int(uint(lo+hi) >> 1) はコメントにあるとおり、uint でキャストすることで、hi が int の最大値に近くともオーバフローしないようにしています。また >> 1 は、大体 / 2 を表しています。
つまり、m は配列全体の大体真ん中ということになります。

3つの要素を並び換え、m1 の位置に中央値を持ってくる処理である、medianOfThree を見ていきます

src/sort/sort.go

// medianOfThree moves the median of the three values data[m0], data[m1], data[m2] into data[m1].
func medianOfThree(data Interface, m1, m0, m2 int) {
    // sort 3 elements
    if data.Less(m1, m0) {
        data.Swap(m1, m0)
    }
    // data[m0] <= data[m1]
    if data.Less(m2, m1) {
        data.Swap(m2, m1)
        // data[m0] <= data[m2] && data[m1] < data[m2]
        if data.Less(m1, m0) {
            data.Swap(m1, m0)
        }
    }
    // now data[m0] <= data[m1] <= data[m2]
}

はい、単純に各々比較し、並び換えているだけですね
コメントにあるとおり、最終的に data[m0] $\leq$ data[m1] $\leq$ data[m2] となるように並び換えています

というわけで、ここまでで data[lo] に pivot にしたい値が入っている状態が作られました

配列を pivot 以上と pivot 以下の部分と pivot より大きい部分に分割する

    // Invariants are:
    //  data[lo] = pivot (set up by ChoosePivot)
    //  data[lo < i < a] < pivot
    //  data[a <= i < b] <= pivot
    //  data[b <= i < c] unexamined
    //  data[c <= i < hi-1] > pivot
    //  data[hi-1] >= pivot
    pivot := lo
    a, c := lo+1, hi-1

    for ; a < c && data.Less(a, pivot); a++ {
    }
    b := a
    for {
        for ; b < c && !data.Less(pivot, b); b++ { // data[b] <= pivot
        }
        for ; b < c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot
        }
        if b >= c {
            break
        }
        // data[b] > pivot; data[c-1] <= pivot
        data.Swap(b, c-1)
        b++
        c--
    }

コメントにある状態を保ちながら並び換えています

pivot を lo に設定し、a を pivot の次の要素、c を配列の最終要素の添字にします

    pivot := lo
    a, c := lo+1, hi-1

pivot 以上の値が表れるまで a を左から右へ動かしていきます
完了すると以下のような状態になります
とくに完了した瞬間は data[a] $\geq$ pivot であることに注意しておきます

| data[a] < pivot |                         まだ不明                     |
0                 a                                                      c

    for ; a < c && data.Less(a, pivot); a++ {
    }

b を a の位置に設定し、pivot より大きい値が表れるまで b を左から右へ動かしていきます
完了すると以下のような状態になります
とくに完了した瞬間は data[b] $>$ pivot であることに注意しておきます

| data[i] < pivot | data[i] <= pivot |             まだ不明              |
0                 a                  b                                   c

    b := a
    for {
        for ; b < c && !data.Less(pivot, b); b++ { // data[b] <= pivot
        }

pivot 以下の値が表れるまで c を右から左へ動かしていきます
完了すると以下のような状態になります
とくに完了した瞬間は data[c - 1] $\leq$ pivot であることに注意しておきます
また data[hi - 1] は pivot と等しい可能性もあります(medianOfThree の処理で data[hi - 1] $\leq$ pivot であることは保証されている)

| data[i] < pivot | data[i] <= pivot |     まだ不明    | data[i] > pivot |
0                 a                  b                 c              hi - 1

        for ; b < c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot
        }

b が c より右に来ていれば完了で、そうでなければループは継続し、b と c を動かしていきます
右側にあって pivot 以下である data[c] と左側にあって pivot より大きい data[b] を交換して次に進みます
ループが完了すると以下のような状態になっているはずです

| data[i] < pivot | data[i] <= pivot           |         data[i] > pivot |
0                 a                           c b                     hi - 1

        if b >= c {
            break
        }
        // data[b] > pivot; data[c-1] <= pivot
        data.Swap(b, c-1)
        b++
        c--
    }

hi - c が小さい場合 pivot と同じ値の区間の始点と終点を返す

c の初期値が hi - 1 であることと、初回のループで c-- されることから、hi-c<3 というコメントに記載されている条件は c がループ初回からずっと data[c] $>$ pivot を満たしていないことがわかります

    // If hi-c<3 then there are duplicates (by property of median of nine).
    // Let be a bit more conservative, and set border to 5.
    protect := hi-c < 5

コードの順とは異なりますが、先にこの条件を満たす場合の処理を読んでいきます

    if protect {
        // Protect against a lot of duplicates
        // Add invariant:
        //  data[a <= i < b] unexamined
        //  data[b <= i < c] = pivot
        for {
            for ; a < b && !data.Less(b-1, pivot); b-- { // data[b] == pivot
            }
            for ; a < b && data.Less(a, pivot); a++ { // data[a] < pivot
            }
            if a >= b {
                break
            }
            // data[a] == pivot; data[b-1] < pivot
            data.Swap(a, b-1)
            a++
            b--
        }
    }

まず、data[b - 1] $=$ pivot が連続して表われている分 b を戻していく
スタート時は以下のような状態になります

| data[i] < pivot | data[i] <= pivot                               | |     |
0                 a                                                c b  hi - 1

完了すると以下のような状態になります

| data[i] < pivot | data[i] <= pivot            | data[i] == pivot |       |
0                 a                             b                  c    hi - 1

        for {
            for ; a < b && !data.Less(b-1, pivot); b-- { // data[b] == pivot
            }

a も data[a] $<$ pivot を満たす間右に動かし、満たさなくなったときにdata[a]とdata[b - 1]を交換します
それがaがb` より右にくるまで続けます
最終的には以下の状態になります

| data[i] < pivot                   | data[i] == pivot             |       |
0                 a                b a                             c    hi - 1

            for ; a < b && data.Less(a, pivot); a++ { // data[a] < pivot
            }
            if a >= b {
                break
            }
            // data[a] == pivot; data[b-1] < pivot
            data.Swap(a, b-1)
            a++
            b--

そして pivot を中央に置いて data[i] $=$ pivot である両端を返したら完了になります

    // Swap pivot into middle
    data.Swap(pivot, b-1)
    return b - 1, c

ちょっと疲れてきたので、雑にいきます...
protect の条件を満たさなくとも、data[i] $>$ pivot である区間が全体の $1/4$ 以下であれば、pivot と等しい区間を調べます
この処理で c は右に移動するので、protect の条件にかからないよう、最後に dups > 1 であればそのまま終了するようにしています

    if !protect && hi-c < (hi-lo)/4 {
        // Lets test some points for equality to pivot
        dups := 0
        if !data.Less(pivot, hi-1) { // data[hi-1] = pivot
            data.Swap(c, hi-1)
            c++
            dups++
        }
        if !data.Less(b-1, pivot) { // data[b-1] = pivot
            b--
            dups++
        }
        // m-lo = (hi-lo)/2 > 6
        // b-lo > (hi-lo)*3/4-1 > 8
        // ==> m < b ==> data[m] <= pivot
        if !data.Less(m, pivot) { // data[m] = pivot
            data.Swap(m, b-1)
            b--
            dups++
        }
        // if at least 2 points are equal to pivot, assume skewed distribution
        protect = dups > 1
    }

    // Swap pivot into middle
    data.Swap(pivot, b-1)
    return b - 1, c

最後!!!

いよいよ大詰めです
mlo mhi に doPivot の結果が入っているので、a から mlo と b から mhi の要素数で小さいほうを quickSort にかけます
さらに、a = mhi と、b が次のループに渡されることでコメントにある通り、quickSort(data, mhi, b) を実行しています
これで再帰的に quick sort の処理が実行され、全体がソートされてめでたしとなります。あーつかれた

        if mlo-a < b-mhi {
            quickSort(data, a, mlo, maxDepth)
            a = mhi // i.e., quickSort(data, mhi, b)

もうちっとだけ続くんじゃ

本当は Slice のソートで reflect パッケージを使っていい感じにしているところの解説までを書きたかったんですが、quick sort の解説だけで力つきてしまいました...(というか途中の論調だと heap sort とかも書く感じですねｗ)
そっちのほうは、また機会があれば...

標準パッケージの中で細かい最適化がちゃんとされているため、ユーザとしては何も考えずに sort.Sort を叩けばよい、というのはよいですね
quick sort の最悪計算時間を利用した攻撃がある、ということが知れたのは非常に面白かったです
あとそもそもアルゴリズムについては学んだことがなかったので色々一気に勉強できたのもよかったです

また、いくつか誤魔化した部分もあるため、ご指摘あればコメントいただけますと幸いです

• shell sort するかどうかの基準が要素数 12 である理由とか
• medianOfThree を medianOfNine にする基準が要素数 40 である理由とか

標準パッケージは Go way を学ぶのに非常によい教材である、というのはよく言われることですので、今後もちょくちょく読んでいければなぁと思います