マージソート(Merge Sort)

2019年11月24日ソート入門, ソート, マージソート, 分割統治法

マージソートとは

マージソートは分割統治法を用いたソートアルゴリズムの1つです。配列を2分割することを繰り返し、小さい配列を一つ一つソートしてから「マージ(併合)」することで、最終的に高速にソートができます。

最終的に1つの要素になるまで分割すれば、ソート済みの長さ1の配列を得ることができるので、あとは「マージ」していくだけでソートが完了します。

アルゴリズム

マージソートは配列を2分割し、それぞれに対してマージソートをするので再帰関数となります。また、2つのソート済み配列を「マージ(併合)」して1つのソート済み配列を作る merge() 関数を使う必要があります。

配列の \(l\) 番目から \(r\) 番目までをソートする merge_sort(arr[], l, r) のアルゴリズムは以下のようになります。

  1. \(mid = (l+r)/2\) とする
  2. merge_sort(\(arr[], l, mid\)) で \(l\) 番目から \(mid\) 番目までソート
  3. merge_sort(\(arr[], mid+1, r\)) で \(mid+1\) 番目から \(r\) 番目までソート
  4. merge(\(arr[], l, mid, r\)) で先程ソートした配列をマージしながらソート

merge() 関数は、2つの配列の最小の要素をそれぞれ比べて、小さい方の要素を配列から取り出して並べていくだけです。

計算量

時間計算量(time complexity)

最悪・平均・最善の計算時間は \(O(n \log n)\) となります。これは \(O(n^2)\) と比べると非常に高速です。

領域計算量 (space complexity)

merge() 関数は、配列の長さ \(n\) のオーダーで新しいメモリが必要となってしまいます。これにより消費メモリは \(O(n)\) となります。

問題例

\(\{3,11,8,24,53,7\}\) と並んだ配列をマージソートする例を考えてみます。以下の図のように分割して、併合するとマージソートの完了です。

Pythonでのプログラム例