【データ構造】適応型マージソート（Adaptive Merge Sort）の仕組みと計算量を徹底解説

適応型マージソート（Adaptive Merge Sort）とは

適応型マージソートは、通常のマージソートと同様にソート済みの部分リストをマージ（併合）していくソートアルゴリズムです。ただし、従来のマージソートが要素数1の部分リストから処理を開始するのに対し、適応型マージソートでは、リスト内にすでに存在する「整列済みの並び」を検出し、そのまとまりをそのまま初期の部分リストとして利用します。これにより、順序が整った要素を無駄に分割・再マージすることなく、マージの回数を大幅に削減できます。

例として、次の図のようなリストを考えてみましょう。このリストは、あらかじめ2つのソート済み部分リストで構成されています。

• 部分リスト1：16, 15, 14, 13
• 部分リスト2：9, 10, 11, 12

部分リスト1は整列していますが、降順（逆順）になっています。そこで、下の図のようにこの部分リストを反転させ、昇順の並びへと修正します。

すべての部分リストが昇順に揃った時点で、マージ処理が開始されます。この例では部分リストが2つしか存在しないため、マージはわずか1回のステップで完了します。マージ結果は次の図の通りです。

設計の考え方

• まず、昇順または降順ですでに整列している部分リストを検出します。
• 降順に並んでいる部分リストが存在する場合は、先頭要素と末尾要素、2番目の要素と末尾から2番目の要素……というように対で交換を行い、リスト全体を反転させます。
• 部分リストが1つだけ残るまで、マージを繰り返して新しい部分リストを作成していきます。

適応型マージソートの計算量分析

適応型マージソートは、要素数1の部分リストから始める代わりに、すでに昇順または降順で整列している部分リストを検出して利用します。初期段階で見つかる部分リストのサイズは、最小で2、最大でm（mは要素数）です。

ただし、部分リストが降順に並んでいる場合は、マージ操作を開始する前にリストを反転する必要があります。この反転には m/2 回の交換操作が要求されます。

最良ケース

リスト全体がすでに昇順または降順に整列している場合、適応型マージソートでは部分リストが1つしか存在しないため、マージ操作は一切不要です。ただし、「すでに整列済みであること」を確認するには O(m) 回の比較操作が必要であり、リストが降順に並んでいる場合にはさらに m/2 回の交換操作が加わります。この性質により、リストが逆順にソートされている場合でも、適応型マージソートは適応的に動作します。

したがって、最良ケースの時間計算量は以下のように求められます。

T(m) = (m−1) + (m/2)
T(m) = (2m − 2 + m) / 2
T(m) = O(m).

なお、適応型マージソートは通常のマージソートと比較して、O(m) の追加メモリ領域を必要とする点に注意してください。

最悪ケース

最悪ケースでは、リスト内に部分的な順序も完全な順序も存在しないため、最初に検出される部分リストのサイズは2になります。部分リストの検出後、マージ処理が開始されます。

• サイズ2の部分リスト同士をマージすると、サイズ4のソート済み部分リストが得られます。
• サイズ4の部分リスト同士をマージすると、サイズ8のソート済み部分リストが得られます。
• このマージのプロセスは、2^k < m が成り立つ限り繰り返されます（kはk回目のマージステップ）。

最悪ケースにおけるマージのステップ数は通常のマージソートと同一であるため、適応型マージソートの最悪ケースの時間計算量はマージソートと同じになります。

T(m) = O(m log m).