ボトムアップマージソート徹底解説：仕組み・擬似コード・実装最適化（トップダウン比較付き）
エバープレイ編集部ボトムアップマージソートとは
ボトムアップマージソート（bottom-up merge sort）は、マージソートの反復（イテレーティブ）版で、配列を段階的に小さなソート済みの塊（ラン）に分け、それらを長さ 1, 2, 4, 8 ... と倍々にマージしていくことで全体を整列するアルゴリズムです。再帰を使うトップダウン方式とは対照的に、スタックフレームを伴わずループで処理するため、実装のオーバーヘッドが小さい点や実行時の挙動が直感的に把握しやすい点が特徴です。
基本的なアイデアと手順
ボトムアップマージソートは次のように動作します。
- 最初は配列を要素ごと（長さ1）を既にソート済みの単位と見なす。
- 現在のラン幅 width を 1 とし、配列の先頭から隣接する 2 つのラン（長さ width の左側と右側）をマージして、長さ 2*width のソート済みランを作る。
- 配列全体を一巡してマージが完了したら、width を 2 倍にし、同様の処理を繰り返す。
- width が配列長 n 以上になったとき、配列は整列済みである。
この操作を行う際、通常は補助バッファ（aux 配列）を用いてマージを行い、パスごとに入力と出力の役割を切り替えます（あるいは都度、結果を元配列へ戻す）。
擬似コード（典型実装）
function bottom_up_merge_sort(A):
n = length(A)
aux = new array[n]
width = 1
while width < n:
i = 0
while i < n:
left = i
mid = min(i + width, n)
right = min(i + 2*width, n)
merge(A, left, mid, right, aux, left)
i = i + 2 * width
// 入力と補助を入れ替える（または aux -> A へコピー）
swap(A, aux) or copy aux to A
width = width * 2
return A
merge 関数は標準的な二つのソート済み部分列を安定に統合する手順です。
計算量・メモリ使用量・安定性
- 時間計算量：最悪・平均・最良ともに O(n log n)。各パスで配列全体の要素をほぼ一度ずつマージし、パス数は ceil(log2 n) であるためです。
- 空間計算量：典型実装では補助配列を1つ用いるため O(n)（外部バッファを除く追加オーバーヘッド）。いくつかのアルゴリズム変形や高度な手法で追加メモリを O(1) に削減することは理論上可能ですが、実装が複雑で現実的には稀です。
- 安定性：マージ処理で等しいキーのときに左側の要素を先に選ぶ実装にすれば安定です。ボトムアップもトップダウンも利用するマージが安定ならば全体として安定なソートになります。
トップダウンマージソートとの比較
- 再帰オーバーヘッド：トップダウンは再帰呼び出しが深さ O(log n) 程度発生するので、関数コールのコストやスタック使用が発生する。ボトムアップはループのみで再帰を用いないため、呼び出しオーバーヘッドがない。
- 実行パターン：ボトムアップはパスごとのマージ幅が決まっておりメモリアクセスが規則的でキャッシュ局所性に有利な場合がある。一方、トップダウンは分割の仕方などで局所性が異なる。
- 最良ケースの扱い：トップダウンは再帰中に小範囲に対して挿入ソートに切り替えるなどの最適化が入りやすい（実際の実装では挿入ソートを組み合わせるのが一般的）。ボトムアップでも同様に小さな幅のときに挿入ソートを使うと高速化できる。
実装上の注意点・最適化
- 補助配列の扱い：パスごとに入力と出力の配列を入れ替える実装（バッファローテーション）を使うとコピーコストを減らせる。ただし最終的な結果がどちらの配列にあるかを管理する必要がある。
- 部分的にソート済みな配列（自然なラン）：実データは連続した昇順の走査区間（natural runs）を持つことが多い。最初に既存のラン長を検出してそのランをマージしていく「自然マージソート」はラン検出によりパフォーマンスが改善される場合がある。
- 挿入ソートとの組み合わせ：幅が小さいとき（例：width <= 32）に挿入ソートで事前に小領域を整列しておくと、総合的に速くなるケースが多い。
- ギャロッピング（Galloping）：連続して一方から多数取る状況では線形探査より指数幅でスキップする戦略（ギャロップモード）が有効で、Timsort に採用されている技術の一部です。
- コピー回数の削減：マージ時に既に右側の全要素が左側より大きく、マージ処理で単純に残りをコピーすればよいような早期終了条件を設けることで無駄な比較やコピーを減らせます。
ボトムアップの利点が活きる場面
- 再帰を避けたい環境（組み込み系や深い再帰が許容されない環境）での利用に向く。
- ループ構造が明確なため SIMD や並列化、外部メモリ（ディスク）上での段階的マージ処理に適用しやすい。
- 安定性を保ったまま確実に O(n log n) を達成したい場合に有用。
外部ソート・並列化との親和性
ボトムアップの考え方は外部マージソート（外部記憶を用いる大規模ソート）に直結します。外部ソートではまずメモリに入るサイズごとに内部ソートを行い、その後 k-way マージを段階的に行っていくため、段階的（ボトムアップ的）なマージ戦略が自然です。
並列化については、マージ自体を並列化する方法（片方の部分列を分割点で二分し、バイナリサーチを使ってもう片方の分割点を求めて独立にマージする）などにより、マルチコアで効率的にスケールさせることができます。分割・マージを再帰的に並列化することで、十分なプロセッサがあればほぼ理想的にスピードアップが得られます。
実運用での注意点と代替案
- メモリ制約が厳しい場合は、追加領域 O(n) を要求する通常のマージソートは不利。メモリをほとんど使わない inplace マージ手法やヒープソート（非安定・O(1)追加）などを検討する。
- 部分的に整列されたデータに対しては Timsort のようにラン検出＋最適化を組み合わせたアルゴリズムのほうが高速なことが多い（Python の sort や Java の一部実装が採用）。
- C++ 標準ライブラリの stable_sort は実装によりマージに基づいた安定ソートが使われることが多い。std::sort は通常 Introsort（クイックソート＋ヒープソート）で、高速だが安定ではない。
まとめ
ボトムアップマージソートは、再帰を用いずに段階的にラン幅を倍にしてマージしていくイテレーティブなマージソートです。時間計算量は O(n log n)、典型的な実装では安定かつ O(n) の追加メモリが必要です。実装が比較的シンプルでキャッシュ局所性や並列化、外部ソートとの親和性が高く、部分的ソート済みデータや実運用での最適化（ラン検出、挿入ソート併用、ギャロッピングなど）を組み合わせることで高性能になります。要件（安定性、メモリ制約、データ特性）に応じてトップダウン型や Timsort、ヒープソートなど代替手法と比較して選択するのが実務的です。
