Merge Sort
マージソート, 併合ソート
Outline
マージソートはDivide and Conquer Approach?に基づくアルゴリズムである.
マージソートはデータ列を二つの部分列に分割し、それぞれの部分列に対して
ソートを行い、全体としてソート済みの列を得る方法である.
二つのソート済み部分列を一つのソート済み列に併合する作業は、
直感的に簡単であることがわかる.
たとえばそれぞれが順序良く並んだ二つのトランプの山を考えてみる.
それらをソートされた一つの山にするには、
二つの山の先頭要素二つから、どちらか小さい方を選ぶことを繰り返していけばよい.
このような併合手法をtwo-way mergeと呼ぶ.
二つより多くの列からデータを併合するような方法を
multiway mergeと呼び、外部ソートでその手法が用いられている.
分割統治に基づくアルゴリズムの特徴として、
その実装は再帰関数を用いることが挙げられる.
このマージソートも一般的には再帰関数を用いて実装するが、
再帰プログラムは計算の順序を変えることで再帰部分を除去することができる.
マージソートの非再帰プログラムは実装もそれほど面倒ではなく
再帰プログラムよりも高速に動作するが、
それほど効果は得られないのでここではソースを示すのみとする.
また、マージソートの特徴として補助記憶領域を必要とすることが挙げられ、
このせいでマージソートは惨めな思いをすることもある(メモリ使うくせに遅いよね).
Program1(Recursive Function)
サイズnの配列dataに対してマージソートを行う関数.
Program2(Nonrecursive Function)
サイズnの配列dataに対してマージソートを行う関数.