python の sort の正体は何なのか？（2）
アドベントカレンダー（自称）vol.21
皆さん、こんにちは。yumyum116 です。SWE転職を目指す者です。
アドベントカレンダーに便乗して、1日1記事投稿に挑戦するとともに、執筆活動の習慣化にも挑戦してみます。
この記事は、プログラミング言語の標準ライブラリの仕様が気になって調べてみたシリーズ第二弾です。
プログラミング初学者の方の参考になれば嬉しいです。
今回は、python で使用可能なソート関数 sort について取り上げます。
1. sort の正体は何なのか
本シリーズの第一弾として投稿した次の記事の中でも触れていますが、python の sort 関数のアルゴリズムはバージョンによって異なります。
バージョン2.3からバージョン3.10までは Timsort、バージョン3.11以降は、Powersort が実装されています。
本記事では、Powersort について取り上げます。
Powersort は、Timsort の run マージ戦略を理論的に洗練させたアルゴリズムで、2018年に提案されました。
「run のマージ順序は、もっと理論的に最適化できるのではないか」
という問題意識から提案されたのが Powersort です。
Powersort 自体は「まったく新しいソートアルゴリズム」ではなく、
- run の生成（自然 run + insertion sort）
- 安定ソート
- マージベースの戦略
といった Timsort の骨格はそのままに、run をどの順番でマージするかという点に焦点を当て、改良を加えています。
2. Powersort のアルゴリズムを読み解く
Powersort を C言語で実装したオリジナルコードはこちらにあります。
オリジナルコードは非常に複雑、かつ C言語で書かれているので、本記事では Powersort の概念を説明しつつ、より簡易的な実装をベースに説明したいと思います。
Timsort における run マージの問題点
Timsort では、run をスタックに積み上げ、次のようなヒューリスティックな不変条件を満たすようにマージを行います。
例（簡略化）：
A > B + CB > C
ここで A, B, C はスタック上の run の長さです。
このルールは経験的に非常によく機能しますが、
- なぜこの条件が良いのか
- 本当に常に最適なマージ順なのか
という点については、理論的な裏付けが弱いという問題がありました。
その結果、
- 特定の run 配列に対しては
→ マージ回数が増える
→ 不要なコピーが発生する
→ 定数倍で遅くなる
というケースが存在します（最悪計算量が破綻するわけではありません）。
Powersort の基本的な発想
Powersort の核心は、次の一点に集約されます。
run を「木構造」として捉え、マージコストが最小になる形を事前に決める
この発想は、次の問題と本質的に同じです。
- Huffman coding
- Optimal binary merge pattern
- Optimal merge tree
つまり、
「サイズの異なる複数の配列を、比較回数（＝コスト）が最小になるようにマージしたい」
という古典的な最適化問題です。
run に「power（階層）」を割り当てる
Powersort では、各 run に対して power と呼ばれる整数値を計算します。
この power は直感的には、
その run が、マージ木のどの高さ（深さ）に属するべきか
を表します。
power は次の情報から決まります。
- 配列全体の長さ
- run の開始位置
- run の終了位置
これにより、
- 配列の左側にある run
- 右側にある run
- 大きな run
- 小さな run
が 二分木上のどこに配置されるべきかが一意に決まります。
Powersort におけるマージ戦略
Powersort のマージルールは、Timsort よりも明確です。
power が同じ run 同士を、できるだけ早くマージする
処理の流れを概念的に書くと、次のようになります。
- run を検出する（Timsort と同じ）
- 各 run に power を計算する
- run をスタックに積む
- スタック上で power の大小関係が崩れたら即マージ
- 常に「浅い木」になるようにマージ順を制御する
この結果、
- マージ木はほぼ最適な形になる
- 不要に深いマージが発生しない
- 比較回数・コピー回数が理論的に抑制される
という性質が得られます。
なぜ速くなるのか（重要）
Powersort が Timsort より速くなる理由は、漸近計算量ではなく定数因子です。
両者ともに、
- 最悪計算量：O(n log n)
- 安定ソート
- 実運用ではほぼ線形時間に近い挙動
という点は変わりません。
しかし Powersort では、
- 無駄なマージが減る
- 小さい run を何度もコピーする回数が減る
- マージ木の高さが抑えられる
結果として、
比較回数・メモリアクセス回数が減少する
という効果が得られます。
これは、Python のように
- 比較が高コスト
- メモリアクセスが相対的に遅い
言語処理系では、特に効いてきます。
Timsort と Powersort の位置づけの違い
まとめると、両者の関係は次のように整理できます。
| 観点 | Timsort | Powersort |
|---|---|---|
| run 検出 | 自然 run | 同じ |
| run ソート | insertion sort | 同じ |
| マージ方法 | 経験則ベース | 理論最適 |
| マージ木 | 暗黙的 | 明示的 |
| 理論的保証 | 弱い | 強い |
| 実装の複雑さ | 高い | さらに高い |
Powersort は、
Timsort を「理論的に完成させたもの」
と考えるのが最も自然です。
3. Powersort も万能ではない
Powersort は理論的に洗練されていますが、万能ではありません。
- run が極端に小さい場合
- ほぼ完全にランダムな配列
- 比較が非常に安価な型（単純整数など）
といったケースでは、
- Timsort とほぼ差が出ない
- 実装コストに見合わない
こともあります。
そのため、
「run が活きるデータ構造かどうか」
「比較・コピーのコストが高いかどうか」
を踏まえたうえで、アルゴリズムを選択する視点が重要になります。
本記事では、Powersort について説明してみました。
初学者でも読める記事を目指したため、内容の厳密さは低いです。
自分の理解が浅いところもあるため、もう少し時間をかけて Powersort を理解した上で、記事の再執筆または加筆修正するかたちで内容をアップデートしたいと思います。
記事内に誤謬等ある場合には、修正いたします。その際は、ご連絡いただけますと幸いです。
それでは、また。
Discussion