整列マージソートは、高速でかつ安定なソートアルゴリズムです。効率はやや劣りますが、クイックソートと比べると実装が簡単で理解もし易いアルゴリズムです。高速で安定という特徴から、様々なところで実用されています。マージソートのアルゴリズムは分割統治法を応用します。マージソートは分割統治法を説明するための最も良い例ともなるので、分割統治法のアイデアもついでに知ることができます。下図は、マージソートの流れを表しています。つの部分配列を統治する。つの部分配列を統治する。つの部分配列を統治する。つの部分配列を統治する。つの部分配列の要素はすでにソート済みである.配列のソートが完了するマージソートの流れの論理的な構造は、ツリー(木)となっていますが、実装するためにツリーのデータ構造を用いる必要はありません。データを配列で処理する場合、マージソートはその倍のメモリ空間を必要とすることが、マージソートの欠点でもあります。実装は以下のように非常にシンプルな構成となります。2つの部分から構成されています。与えられた配列を前半後半の2つに分割します。行います(再帰により実現する)。以下のときは何もせずに終了します。ソートされている部分配列の前半と後半に対して実行されます。役割は、すでにソートされている2つの部分配列を1つのソートされた部分配列にすることです。関数は番兵を使ってやや巧妙な処理をしています。メカニズムをカードの操作で表したものです。左右にカードの束があり、各束のカードは小さい順に整列されているものとします。カードの最下部に番兵としてジョーカーを追加配置します。マージの処理は、各カードの山のてっぺんの値を比べ、小さい方を選択して順番に並べていきます。この操作の過程で、あるカードとジョーカーを比べる局面が発生しますが、ジョーカーが選ばれることはありません。番兵にはどのカード(数字)と比べても負けることのない大きな数を割り当てるのです。ジョーカーすなわち番兵の設置によって、マージの際にカードの束が空になったか否かのチェックをする必要がなくなります。カードを選択する回数を、ジョーカーを除いたカードの合計値とすれば、ジョーカーが比べられることも、カードの束が空になることもないからです。束が空になったか否かのチェックは、プログラム上では配列の範囲を超えるか否かのチェックとなるので、番兵の設置は処理の高速化にも繋がり(微々たるものですが、)プログラムが読みやすくなります。プログラムは、さらに巧妙なテクニックを用いています。プログラムの動作を考えてみましょう。回の比較演算がなされるからです。アイデア、などを学べる良いアルゴリズムの1つではないでしょうか。masimarock。