ソートアルゴリズムのマージソート（Mergesort）解析

no_mkd

一.マージソートの長所と短所（pros and cons）

苦労して理解するにも、理由が必要でしょう：

• マージソートの効率はピークに達しています：時間計算量は O(nlogn) で、これは比較ベースのソートアルゴリズムが達成できる最高境界です
• マージソートは安定したアルゴリズムです（つまり、ソート過程で大小が同じ要素はソート前の順序を維持できます。3212 を昇順ソートした結果は 1223 で、ソート前後の 2 つの 2 の順序は変わりません）。この点はあるシナリオで極めて重要です
• マージソートは最も一般的な外部ソート方法です（ソート対象のレコードが外部記憶装置にあり、メモリにすべてのデータを収容できない場合でも、マージソートは引き続き適用可能です。もちろんマージソートは内部ソートにも同様に適用可能です...）

短所：

• マージソートには O(n) の補助スペースが必要で、これと効率が同じクイックソートとヒープソートはそれぞれ O(logn) と O(1) の補助スペースが必要です。同種のアルゴリズムの中でマージソートの空間計算量はやや高めです

P.S.本記事では最も原始的な「二路マージ」のみを議論し、多路のものはこれと類似しています

二.内部原理

まずマージソートの考え方は：分割統治法であり、クイックソートの考え方と同じです

アルゴリズムの考え方：無秩序 -> 部分的に有序 -> 全体的に有序

マージソートにおける「分割」と「結合」の過程は一緒に結合されており、つまり各ラウンドで「分割」と「結合」の作業を行っており、先に「分割」し終わってから「結合」するのではありません（「分割」は非常にシンプルで、ただ二分し続けてこれ以上分割できないまでというだけだと思えば、それは間違いです。分割したら結合できなくなります。「分割」と「結合」は一緒に結合されていることを覚えておいてください）

マージソートの過程を 1 枚の図で説明するだけで十分です：

説明：P1 と P2 を比較し、大きい（小さい）方を P に装入し、その後 P1 または P2 を右に移動し（誰を装入したかを移動）、最後に P を右に移動します

例えば配列 a[n] を昇順ソートする場合、具体的な過程は以下の通りです：

1. 長さがどちらも n/2 の 2 つの補助スペースを申請し、a 配列を装入します。前半を L に、後半を R に装入します
2. 説明中の方式で 1 ラウンドの比較を行います（P が A から C に移動し、1 ラウンド終了）

ここで 1 ラウンドのソートを終えて何が得られたかを考えてみましょう：

1. 部分的に有序を達成しました（前半 < 後半、对吧？）
2. それに加え、非常に自然にソート対象シーケンスを二つに分け、再帰の準備をしました

まだはっきりしませんか？ではさらに数言あります：

1. 図示の過程はなぜ長さ n の補助スペースが必要かを説明しています
2. L と R がそれぞれ内部で有序であれば（同じ昇順または同じ降順）、その後 1 ラウンドのマージを経るだけでソートが完了します（よく考えてみてください、間違いないでしょう？）
3. ソート部分がマージ部分です（上で述べたあの言葉を覚えていますか？「分割」と「結合」の過程は一緒に結合されており、決して分けて考えてはいけません。さもないと結合できなくなることに気づくでしょう...）

三.実装の詳細

上記の説明がまだはっきりしない場合、例を挙げて一歩ずつ分析しましょう：

ソート対象シーケンスが a[] = {3, 2, 1, 4} と仮定すると、具体的な過程は以下の通りです：

P.S.ソート対象シーケンスが奇数個の場合はどうするか？これは問題ですか？単に分割された前半が後半より 1 つ少ないだけで、単独ラウンドのループ制御は P ポインタによって行われるため、ある P1 に対応する P2 が比較できないという問題は存在しません

四.まとめ

マージソートは外部ソートが必要なシナリオで多く使用され、それ以外に内部ソートで安定性を保証する必要がある場合もマージソートを採用します（安定性を要求しない内部ソートは一般的にクイックソートまたはヒープソートを使用します。前者はソート対象シーケンスが基本的に有序の場合に効率が低く、後者はヒープのメンテナンスが問題となります）