自然マージソートとは？ラン検出で高速化する仕組み・計算量・実装最適化とTimsortの関係
エバープレイ編集部自然マージソートとは — 概要
自然マージソート（Natural Merge Sort）は、配列やリスト内に既に存在する単調増加（あるいは単調減少）の「ラン（run）」を利用してソートを高速化するマージソートの変種です。基本的な考え方は簡単で、入力を左から走査して連続した既に整列された区間（ラン）を切り出し、そのラン同士を順にマージしていくことで全体を整列する、というものです。
基本的な仕組み
従来の（標準的な）マージソートは配列を半分に切って分割し、再帰的にソートしてからマージします。一方、自然マージソートは「分割を固定的に二等分する」のではなく「元のデータに存在する整列区間（run）を分割単位として使う」点が異なります。
- 入力を左から右に一度スキャンして、連続して増加（または減少）している部分列を1つのランとして抽出する。
- 抽出したランをキューやスタックに順次積み上げ、隣り合うラン同士を取り出してマージする。
- ランの個数が1つになるまでマージを繰り返す。
データが既に部分的に整列されている場合、ランの数が少なくなるため、必要なマージ回数（＝ツリーの高さ）が小さくなり、全体の作業量が減ります。理論的にはランの個数を r とすると計算量は O(n log r) となり、最良の場合（既に全体が整列されている＝ r=1）で O(n) を達成できます。一方、最悪ケースはランがほぼ要素ごとに分かれる場合で O(n log n) です。
アルゴリズムの詳細
典型的な実装手順は次の通りです。
- 配列を左から走査し、連続する非減少（または非増加）区間を1つのランとして識別する。非増加のランが見つかったら、そのランを反転して非減少に揃える実装が多い（安定にするためなど）。
- 検出したランをキュー（FIFO）やスタック（LIFO）に格納する。
- データ構造から取り出した隣接するラン同士を通常の二つ組のマージで結合する。結合後のランを再び構造に戻す。
- ランが1つになるまでマージを続ける。
マージの順序（どのランをどの順番でマージするか）は最終的な比較回数に影響します。極端に偏ったマージ順だと、長さのバランスが悪く効率が落ちます。実装によってはマージ順を調整するヒューリスティック（最小ヒープで短いラン同士を先にマージする、あるいは Timsort のようなスタック不変式）を用いて性能を改善します。
擬似コード（簡易版）
function natural_merge_sort(A):
runs = []
i = 0
while i < len(A):
j = i + 1
while j < len(A) and A[j-1] <= A[j]:
j += 1
add run A[i:j] to runs
i = j
while len(runs) > 1:
newRuns = []
for k in range(0, len(runs), 2):
if k+1 < len(runs):
newRuns.append(merge(runs[k], runs[k+1]))
else:
newRuns.append(runs[k])
runs = newRuns
return runs[0]上は最も素朴な実装で、隣接するランを順にマージしています。実運用ではマージ順やラン検出で追加の工夫を施します。
計算量・安定性・メモリ使用量
- 計算量：最良ケース O(n)（すでに完全に整列されている場合：1つのランだけ）／平均・最悪ケース O(n log n)。詳しくはラン数 r に依存し O(n log r)。
- 安定性：本質的に安定（同値要素の相対順序を保持）に実装可能。標準的なマージ操作自体が安定であるため。
- 追加メモリ：典型的には O(n) の補助配列を使う（外部に出力する形でマージするため）。インプレースでのマージは可能だが実装が複雑で性能上のトレードオフがある。
実装上の注意と最適化
実装時に性能向上・安定性確保のためよく行われる工夫は次の通りです。
- 下降ランの反転：入力で下降（非増加）しているランを検出したら反転して昇順に揃える。これによりランが長くなりマージ回数が減る。
- マージ順の調整：ラン長のアンバランスを避けるために、短いラン同士を先にマージする、またはスタック不変式（Timsort のような）を採用する。
- 閾値以下の短いランは挿入ソートで延べしてからマージする：短いランに対しては挿入ソートの方が高速なことが多く、これを組み合わせると実運用での定数因子が小さくなる。
- ギャロップ（Galloping）モード：マージ中に片方から連続して多く取り出せる場合、二分探索などで一気に取り出すテクニック（Timsort に採用）。
自然マージソートと Timsort の関係
Timsort は Python（CPython）や Java の一部実装で採用されているソートアルゴリズムで、自然マージソートの考え方（ラン検出・ランのマージ）を中心に多くの実用的最適化を組み合わせたものです。Timsort はラン検出、ラン反転、最小ラン長（minrun）、スタック不変式によるマージ順制御、ギャロップモードなどを導入し、安定で実用的な性能を実現しています。したがって、Timsort は「自然マージソートを強化した実用版」とみなせます。
いつ使うべきか（利点・欠点）
- 利点
- 入力が部分的に整列されている場合に非常に高速（適応的）。
- 安定ソートであり、安定性を必要とする用途に適する。
- 実装は比較的シンプルで外部ソート（ディスク・テープを使った大規模データのソート）にも応用しやすい。
- 欠点
- 最悪ケースは従来のマージソートと同様に O(n log n)。
- 補助配列を必要とすることが多く、メモリ使用量が増える。
- ランが短く多数になった場合は、他のアルゴリズム（例えば最適化されたクイックソートやヒープソート）が競合することもある。
外部ソートとの関係
外部メモリ上でのソート（ディスクやテープを用いる大規模データのソート）においても自然マージのアイディアは重要です。外部ソートではディスクから読み出す塊（ラン）をまず作成し、それらを段階的にマージしていきます。外部ソートにおける「置換選択法（replacement selection）」などは長いランを生成するための手法で、ランを長く作れるほどマージ段数が減り I/O が節約されます。自然マージのラン利用の考え方はこの分野と親和性が高いです。
簡単な例
配列 [1, 3, 5, 2, 4, 6, 0, 7] を考えます。走査してランを検出すると次のようになります。
- ラン1: [1, 3, 5]
- ラン2: [2, 4, 6]
- ラン3: [0, 7]
これらを順にマージしていくと、まずラン1とラン2をマージして [1,2,3,4,5,6]、続いてそれをラン3とマージして完全に整列された配列を得ます。ラン数が小さいため効率的です。
実際の採用例
自然マージソートそのものの派生や概念は、多くの実用的なソートアルゴリズムやライブラリに影響を与えています。特に Timsort（Python のソート、Java の一部のオブジェクト配列ソート）が自然ランの検出と利用、ランの最適なマージ順制御を取り入れている点は注目に値します。
まとめ
自然マージソートは、入力の部分的な整列を活かして高速化する「適応的な」マージソートです。ランの数 r に依存して O(n log r) の性能を示し、完全に整列されている場合は O(n) を達成します。安定で外部ソートにも応用しやすい一方、補助メモリを要する点には注意が必要です。実務では Timsort のような自然マージのアイディアを発展させた実用アルゴリズムが多く使われているため、部分ソート済みデータの扱いやライブラリ選定の際に自然マージ的アプローチの利点を考慮する価値があります。
