データ構造における適応型マージとソート

アダプティブマージソート

アダプティブマージソートは、ソートされたサブリストのマージソートを実行します。ただし、最初のサブリストのサイズは、サイズ1のサブリストではなく、要素のリスト間の順序の存在に依存します。たとえば、図のリストについて考えてみます。

2つのソートされたサブリストで構成されています。

• 要素16、15、14、13を含むサブリスト1。
• 要素9、10、11、12のサブリスト2。

サブリスト1はソートされていますが、逆の順序になっています。したがって、サブリスト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のソートされたサブリストになります。
• マージのプロセスは、2k

アダプティブマージソートの最悪の場合のマージ手順は、マージソートと同じです。したがって、アダプティブマージソートの最悪の場合の時間計算量は、マージソート-

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