導入：スターリンソートのおさらいと、後続システムがクラッシュする問題
「スターリンソート（Stalin Sort）」というアルゴリズムをご存知だろうか。
通常のソートアルゴリズムは、要素同士を比較し、順序が崩れていれば「入れ替える」ことで整列を実現する。しかしスターリンソートは違う。順序に反する要素を見つけたら、それを入れ替えるのではなく、列から粛清（削除）する。残った要素は、定義上必ず昇順に並んでいる。比較1回につき削除するかしないかを決めるだけなので、計算量は驚異のO(n)。史上最速のソートである。
入力: [1, 3, 2, 4, 6, 5, 7]
処理: 3の後の2は「秩序を乱す反動分子」→ 粛清
6の後の5は「秩序を乱す反動分子」→ 粛清
出力: [1, 3, 4, 6, 7] ← 確かにソートされている美しい。だが問題がある。入力が7要素だったのに出力は5要素だ。この配列を受け取った後続システムは「あれ、2つ消えてる」と気づき、インデックス参照でクラッシュするか、あるいは「歴史的に何も問題は起きていない」という体でそのまま処理を続けるかのどちらかになる。後者の方がずっと恐ろしい。
この記事では、この「粛清によるソート」を実装するにあたって、なぜGo言語がこれ以上ないほど適した言語であるかを、Goの低レイヤーな仕様——スライス、range、goroutine——に沿って解説する。同志スターリンがもしプログラミング言語を選ぶとしたら、間違いなくGoを選ぶはずだ。理由を見ていこう。
第一章：Goのスライスという免罪符
Goのスライスは、内部的には次の3つの要素を持つ構造体にすぎない。
type sliceHeader struct {
Data uintptr
Len int
Cap int
}
重要なのはここだ。スライスの「長さ」は、単なる整数の記録にすぎず、背後の配列そのものを書き換えなくても改ざんできる。
append を使って要素を除外するとき、Goは元の配列を必ずしもコピーしない。同じメモリ領域の上で、ただ Len という記録だけを書き換える。
package main
import "fmt"
func stalinSort(nums []int) []int {
if len(nums) == 0 {
return nums
}
purged := nums[:1]
last := nums[0]
for _, v := range nums[1:] {
if v >= last {
purged = append(purged, v)
last = v
}
}
return purged
}
func main() {
history := []int{1, 3, 2, 4, 6, 5, 7}
fmt.Println("粛清前の記録:", history)
official := stalinSort(history)
fmt.Println("公式な記録 :", official)
fmt.Println("背後の配列 :", history[:len(history)])
}
history というオリジナルの配列は、公式記録である official を生成する過程でその場で書き換えられる。歴史修正主義とは、まさにこの「新しいデータのために古いデータの入れ物を再利用する」行為そのものだ。しかも新しい配列を確保しないので、GCへの負荷もない。実に効率的な粛清である。
第二章：rangeによる安全な統治
ここで一つ、Goのforループ構造について触れておく必要がある。もしうっかり、イテレート中のスライス自体を直接書き換えながら粛清しようとすると、何が起きるか。
func dangerousStalinSort(nums []int) []int {
for i := 0; i < len(nums); i++ {
if i > 0 && nums[i] < nums[i-1] {
nums = append(nums[:i], nums[i+1:]...)
i--
}
}
return nums
}
この実装は一見動くように見えて、i-- を忘れる、あるいは range で回している最中に長さを変えてしまうと、粛清されたはずの要素を読み飛ばしたり、逆に粛清が甘くなったりする。つまり「統治が不安定」になる。粛清はきっちり、モレなく実行されなければならない。
Goの range は、ループ開始時点でのスライスの長さと先頭ポインタをスナップショットとして固定する（正確には、range式は評価時に一度だけ評価される）。つまり、ループの中で purged という別の入れ物に安全に「承認された者」だけを積み上げていく統治スタイルが、Goのイディオムとして自然に導かれる。
func stableStalinSort(nums []int) []int {
if len(nums) == 0 {
return nil
}
result := make([]int, 0, len(nums))
result = append(result, nums[0])
for _, v := range nums {
if v >= result[len(result)-1] {
result = append(result, v)
}
}
return result
}
range nums は「粛清対象リストの原本」を安全に舐め続け、result という「新体制の公式記録」だけを別途構築する。原本と新体制の記録を明確に分離することで、バグという名の反乱が起きる余地をなくす。これがGoの range がもたらす、後続処理にとっての堅牢な統治構造である。
第三章：Goroutineによる大粛清
ここまでは1つの列に対する処理だった。しかし本当の粛清は、大規模データに対して一瞬で完遂されねばならない。100万件のデータを愚直に1つのゴルーチンで舐めていては、五カ年計画どころか五十年かかってしまう。
そこでGoroutineの出番だ。データを複数のブロックに分割し、各ブロックを並行して粛清（部分ソート）し、最後に統合する。
package main
import (
"fmt"
"sync"
)
func chunkStalinSort(nums []int) []int {
if len(nums) == 0 {
return nil
}
result := make([]int, 0, len(nums))
result = append(result, nums[0])
for _, v := range nums[1:] {
if v >= result[len(result)-1] {
result = append(result, v)
}
}
return result
}
func merge(a, b []int) []int {
merged := make([]int, 0, len(a)+len(b))
i, j := 0, 0
for i < len(a) && j < len(b) {
if a[i] <= b[j] {
merged = append(merged, a[i])
i++
} else {
merged = append(merged, b[j])
j++
}
}
merged = append(merged, a[i:]...)
merged = append(merged, b[j:]...)
return merged
}
func greatPurge(data []int, workerCount int) []int {
n := len(data)
if n == 0 {
return nil
}
chunkSize := (n + workerCount - 1) / workerCount
results := make([][]int, workerCount)
var wg sync.WaitGroup
for w := 0; w < workerCount; w++ {
start := w * chunkSize
if start >= n {
break
}
end := start + chunkSize
if end > n {
end = n
}
wg.Add(1)
go func(idx int, chunk []int) {
defer wg.Done()
results[idx] = chunkStalinSort(chunk)
}(w, data[start:end])
}
wg.Wait()
final := results[0]
for i := 1; i < len(results); i++ {
if results[i] != nil {
final = merge(final, results[i])
}
}
return final
}
func main() {
data := []int{5, 1, 9, 2, 8, 3, 7, 4, 6, 10, 0, 15, 12, 20, 11}
fmt.Println("処理前の全国データ:", data)
official := greatPurge(data, 4)
fmt.Println("大粛清後の公式記録:", official)
}
ここで注意すべき点が一つある。各Goroutineは自分が担当するブロックの中でしか粛清を実行できない、ということだ。つまりブロック分割の境界をまたいだ「秩序の乱れ」は、最初の並行処理では検出できず、最後の merge フェーズで初めてつじつまを合わせることになる。
これは実によく出来た比喩でもある。地方の粛清は地方委員会の裁量に任され、中央委員会（メインGoroutine）は最後に届いた報告書を統合するだけ——各地でどれだけの「反動分子」が粛清されたか、中央は関知しない。sync.WaitGroup は、全ての地方委員会からの報告（wg.Done()）が揃うまで、中央委員会（mainゴルーチン）を待機させる。これ以上ないほど的確な同期プリミティブの使い方だ。
まとめ
O(n)という計算量は伊達ではない。1回の走査で、比較して、残すか消すかを決めるだけ。そこにGoの「値は基本コピー、スライスは参照的に振る舞う」という独特な仕様と、goroutineによる気軽な並行処理が組み合わさることで、低コストかつ高速に「望ましい順序」だけを残すソートアルゴリズム（極めて実用的な粛清機構）が実装できるのである。
