多路マージ（k-way マージ）入門：ヒープとルーザーツリーによる実装・外部ソートとLSMツリーの最適化
エバープレイ編集部多路マージとは
多路マージ（たろ・マージ、k-way merge）は、複数（k個）の既にソートされた入力列を一つのソート済み列に統合するアルゴリズム群を指します。2路（2-way）マージがマージソートの典型的な一部であるのに対し、多路マージはk > 2 の任意の数のソート済み列を同時にマージする一般化です。複数のソースから順序を保ちながらデータを結合する必要がある場面、特に入力データがメモリに収まらない外部ソートやデータベースのマージ操作、検索エンジンのインデックス構築、LSMツリー（LevelDB/ RocksDB 等）のコンパクションなどで広く用いられます。
基本的な考え方と代表的な実装法
多路マージの目的は各入力列の先頭要素を比較しながら最小（または最大）の要素を順に出力していくことです。代表的な実装法をいくつか挙げます。
最小ヒープ（priority queue）を使う方法：各入力列の先頭要素を最小ヒープに入れておき、ヒープから最小要素を取り出すたびにその要素が属していた入力列の次の要素をヒープに挿入します。要素総数を N、入力列数を k とすると、ヒープ操作（挿入・削除）は O(log k) で、全体で O(N log k) の時間でマージできます。実装が簡単で汎用的なため一般によく使われます。
トーナメント木・ルーザーツリー（loser tree）：比較回数の定数係数を小さくするためのデータ構造です。完全二分木の各内部ノードに「敗者（loser）」を格納し、根に勝者（最小値）を保ちます。要素を1つ取り出して置換するときは木の高さに比例した比較で済み、操作あたり O(log k) の比較回数で済む点はヒープと同じオーダーですが、実際の比較回数が少なく局所性も高いため高速になることが多いです。外部ソート実装で好まれる方式の一つです。
分割統治・逐次マージ：k個を二分木状にペアごとにマージしていく方法（マージツリー）や、単純に1つずつ順にマージしていく方法もありますが、後者は効率が悪く（総時間が O(kN) に近くなる場合がある）、前者はマージツリーの深さに依存して効率が変わります。大規模データや外部メモリでは最小ヒープやルーザーツリーの方が一般に有利です。
計算量とメモリ（内部メモリでの解析）
k 個のソート済み配列の総要素数を N とすると、最小ヒープまたはルーザーツリーを使った多路マージの時間計算量は O(N log k) です。k = 2 の場合は O(N)（2-way マージ）になり、k が増えるほどログ項が増えるものの、k を大きく取ることでマージ回数（パス数）を減らせるトレードオフがあります。
メモリ面では、基本的に各入力列につき少なくとも1つの要素（または1つの入力バッファ）を保持する必要があります。内部メモリ型の単純な実装であれば O(k) の補助領域（ヒープやツリー用の配列）と、各入力列の現在位置情報があれば良いです。
外部ソート（外部メモリ）における多路マージ
多路マージが最も重要になるのは外部ソート（データ全体がメモリに入らない場合）です。外部ソートは一般に「ランの生成（initial run generation）」→「複数回のマージパス」で行います。外部モデルでは I/O（ディスクアクセス）が主要なコストであり、多路マージは I/O を減らすための重要な手段です。
ランの生成：入力をメモリにできるだけ読み込み、内部ソート（例えばメモリ上でのクイックソート・ヒープソート）してソート済みのラン（部分ファイル）としてディスクへ書き出します。置換選択（replacement selection）を使うと平均ラン長を伸ばして初期ラン数を減らせます。
k-way マージパス：ディスク上に R 本の初期ランがあるとき、各マージパスで k 本ずつマージできれば、パス後のラン数は ceil(R/k) になります。したがって必要なパス数は概ね ceil(log_k R) です。パス数を減らすために k を大きく取りたい一方で、同時に k+1（入力 k 個 + 出力1個）のバッファが必要でありメモリとのバランス調整が必要です。
I/O 最適化：各入力・出力をブロック単位でバッファリングしてランをまとめて読み書きすることでランダムアクセスを避け、ディスクや SSD の性能を引き出します。ルーザーツリーは比較回数を抑えつつ、入力バッファを小さいまま扱えるので外部ソートでよく使われます。
ポリフェーズ（polyphase）マージ：限られた数の磁気テープ時代からある最適化手法で、ランを不均衡に配分してダミーランを減らすことでトータルのパス数・I/O を抑えるテクニックです。ディスクベースの実装ではバッファ管理が柔軟なため必ずしも常用されませんが、理論的な選択肢として知られています。
実務での応用例
データベースのソート・マージジョイン：大規模な結合処理では各テーブルをソートしてからマージするマージジョインが効率的です。多路マージは複数ソート済みランの統合に使われます。
LSMツリー（LevelDB, RocksDB など）のコンパクション：複数の SSTable（ソート済みファイル）をマージして新しいレベルを作る際に多路マージが使われます。時間複雑度とI/O、書き込み増幅（write amplification）を下げることが重要です。
検索インデックスのマージ：複数の部分インデックスを統合する作業（インデックス構築・更新）で多路マージが使われます。倒置リストのマージなどが代表例です。
MapReduce や外部ログ処理：分散処理の中間結果をマージして最終的な集約を行う場面でも k-way マージは利用されます。例えば各マップタスクが出力したソート済みチャンクをレデュースでマージする場合などです。
実装上の注意点とチューニング
k の選び方：内部メモリが十分にあるなら k を大きくしてマージパス数を減らすと I/O（ディスクベースではパス数に相当）が減りますが、各入力に対するバッファやヒープ／ツリーのオーバーヘッドを考慮する必要があります。実務では「バッファサイズ × (k + 1) が使用可能メモリに収まる」ことを基準に k を決定します。
安定性：多路マージ自体は安定に実装できます。等価キーが複数の入力にまたがる場合、安定性を保つには等しい場合にどちらの入力を先に出すかの方針（たとえば先に来た入力列を優先）を一貫して適用します。ヒープに格納する際に（値, 入力ID, 元の順序）などのタプルで比較すると安定性を保てます。
重複の扱い：重複要素を除去したい場合は、出力時に前回出力した値と比較する方法が一般的です。合計やカウントなどを計算する場合は、等値辺りの集約ロジックを組み込めます。
バッファリングとブロックI/O：外部ソートでは小さすぎる単位でI/Oを行うと大幅に遅くなるため、読み込み・書き込みはブロック単位（例えば数キロバイト〜数メガバイト）で行うべきです。ダブルバッファリングや非同期I/Oを使ってI/O待ちを隠蔽すると良いでしょう。
並列化：マルチスレッド環境では複数の入力列の読み取りや、複数グループの並列マージを実行することでスループットを改善できます。ただしディスクI/Oやメモリバンド幅がボトルネックになりやすい点に注意してください。
設計上のトレードオフまとめ
多路マージの採用では以下のトレードオフを考慮する必要があります。
- k を大きくするとマージパス数は減るが、メモリ消費（バッファ＋データ構造）が増える。
- ヒープは実装が容易だが、ルーザーツリーは比較回数や局所性の面で有利な場合がある。
- 外部ソートではI/O効率（ブロックサイズ、バッファ戦略）が実行時間を大きく左右する。
- 安定性や重複の扱いはアプリケーション要件に合わせて実装方針を明確にする。
簡単な例（概念）
3つのソート済み配列 A, B, C をマージする場合、各配列の先頭要素を最小ヒープに入れておき、最小の要素を取り出して出力し、その要素を取った配列の次の要素をヒープに入れる操作を繰り返します。ヒープサイズは常に最大 k（この例では 3）で、各要素について O(log k) の操作が発生するため総計 O(N log k) になります。
まとめ
多路マージは複数のソート済みストリームを効率的に統合するための基本的かつ重要な技術です。内部メモリでの実装にはヒープやルーザーツリーがあり、外部ソートやデータベースのマージ、検索インデックス構築、LSMツリーのコンパクションといった大規模データ処理で不可欠です。設計では k の取り方、バッファリング、I/O の最適化、安定性の要件を慎重に検討する必要があります。
参考文献
- 多路マージ - Wikipedia（日本語）
- K-way merge algorithm - Wikipedia (English)
- Loser tree - Wikipedia (English)
- External sorting - Wikipedia (English)
- Replacement selection - Wikipedia (English)
- Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching（参考書籍）
投稿者プロフィール
