k-wayマージ入門：計算量（O(N log k））からヒープ・敗者木実装、外部ソートとI/O最適化まで
エバープレイ編集部k-wayマージとは何か
k-wayマージ（k-way merge）は、k個のソート済みシーケンス（配列、リスト、ファイルなど）を一つのソート済みシーケンスに統合するアルゴリズム群の総称です。2-way（2つ）マージは古典的なマージ操作ですが、k > 2 の場合でも同様の概念を拡張して適用します。k-wayマージは内部メモリでの複数列の結合や、外部ソートにおけるディスク上の複数ラン（run）の統合など、実務で広く使われます。
基本的な考え方と複雑度
全体の要素数を N、入力列数を k とすると、最も一般的な実装（ヒープやトーナメント木を使う）では計算量は O(N log k) です。各出力要素を取り出す際に、どの入力列の先頭が最小（もしくは最大）かを決定する必要があり、その選択操作が log k のコストを要します。メモリ使用量は各列の「先頭要素」を保持するための O(k)、および必要に応じてバッファサイズ分の追加メモリが必要です。
代表的な実装方式
優先度付きキュー（ヒープ）を使う方法
各入力列の先頭要素を (値, 列ID, 追加情報) のタプルとして最小ヒープに格納します。取り出した要素を出力し、その要素を取り出した列から次の要素をヒープに挿入する操作を繰り返します。実装が単純でライブラリの優先度付きキューを使えるため、実務で最も多く用いられます。
トーナメント木（loser tree / winner tree）を使う方法
トーナメント木は k 個の入力から最小値を決めるための完全二分木構造で、更新時の比較回数を減らす目的で用いられます。特に「loser tree（敗者木）」は更新時に行う比較が少なく、ヒープと比べて実測で高速なことが多いです。更新のコストは O(log k) ですが、一定係数が小さいのが利点です。
分割・再帰的ペアワイズマージ（バランスされた木構造）
k個を二分木状に組んで再帰的にマージしていく方法です。総コストは O(N log k) で、実装次第ではメモリ局所性が良くなりますが、メモリ/コピーのオーバーヘッドに注意が必要です。
外部ソートとk-wayマージ
外部ソート（ディスク上の非常に大きなデータをソートする技術）では、メモリに収まらないため「生成（run）の作成」と「多重マージ」のステップに分かれます。まず入力をメモリ内でソートしたチャンク（run）をディスクに書き出し、次にこれらのランをk-wayマージして最終的なソート結果を得ます。ここでのkは同時に開けるファイル数やバッファ数、利用可能なメモリに依存します。一般に、より大きなkを取ればマージパスの回数が減りますが、各ランのバッファ確保やI/O操作の効率とのトレードオフがあります。
実用上の工夫（バッファリングとI/O）
- 各入力ファイル（ラン）に対してバッファを用意し、ディスクI/Oはブロック単位でまとめて行う。小さすぎるとI/Oが頻発し性能が悪化する。
- 出力側もバッファを持ち、ある程度溜まってからディスクへ書き出す。
- replacement selection を使うと初期ランの平均長をメモリサイズの約2倍程度まで伸ばせる（理論上の期待値であり実装やデータ分布に依存）。
安定性（stable merge）と重複キーの扱い
マージを「安定」に保つことは重要な要件になることがあります。安定性を保持するためには、キーが等しい場合に入力列の順序を保つように、優先度比較に列IDやインデックスを副キーとして組み込む実装が一般的です。たとえばヒープに格納するタプルに (キー, 列ID, 元の順序) を含めることで安定性を確保できます。
並列化とスケーラビリティ
k-wayマージは単純な逐次アルゴリズムですが、並列化の方法も存在します。代表的な手法：
- キー範囲で分割（レンジパーティショニング）して各スレッド/ノードで独立にマージする。各パーティションは並列で処理できる。
- 大規模分散環境では、各ワーカーで部分マージを行い、最終的にさらにマージする多段階アプローチ（MapReduce や Spark の shuffle と sort の仕組み）をとる。
- マルチスレッド環境では、入力をチャンク化して並列にマージし、結果を段階的に結合する方法がある。ただしI/O帯域やメモリの共有に注意が必要。
具体的な実装例（概念的）
簡単なヒープベースの擬似コード：
heap = empty
for i in 1..k:
if input[i] not empty:
heap.push((input[i].pop_front(), i))
while heap not empty:
val, i = heap.pop_min()
output.push(val)
if input[i] not empty:
heap.push((input[i].pop_front(), i))
言語別ライブラリ例：
- Python: heapq.merge(*iterables) — 複数のソート済イテレータを遅延でマージする関数（内部でヒープを使用）。
- Java: 標準ではk-wayマージ関数はないが、PriorityQueue を用いて簡単に実装できる。
- C++: 標準ライブラリの std::merge は二つの範囲をマージする関数。k-way マージは priority_queue 等で自前実装するか、外部ライブラリを利用する。
注意点と落とし穴
- k をむやみに大きくすると、各ランのバッファが減って逆にI/Oが増える可能性がある。
- メモリが不足するとディスクスワップが発生し極端に遅くなるため、バッファ割当ては慎重に。
- ストリームの終端（空になった入力）やエラーハンドリング、空データ列の扱いを実装で確実に行う。
代表的な利用例
- データベースの外部ソートやクエリ実行計画（大規模ソート、外部マージジョイン）
- 分散処理フレームワーク（Hadoop/Spark）のシャッフル後のマージ
- ログやタイムシリーズデータの複数ソース統合
- 複数ソート済ファイルのマージ（バッチ処理、バックアップの統合）
まとめ
k-wayマージは「複数のソート済シーケンスを効率よく結合する」ための基本的かつ重要な技術です。実装選択（ヒープ、トーナメント木、バランスされたペアワイズマージ）やバッファリング戦略、I/O効率、安定性確保などの工夫により、実際の性能は大きく左右されます。特に外部ソートや分散ソートの場面では、k の選び方とバッファ設計が性能の鍵になります。
参考文献
- External sorting — Wikipedia
- Loser tree — Wikipedia
- Replacement selection — Wikipedia
- heapq.merge — Python 3 Documentation
- std::merge — cppreference.com
- PriorityQueue (Java SE 8) — Oracle Docs
- Hadoop MapReduce Tutorial — Hadoop Official Docs
投稿者プロフィール
