マージソート

整列してある2つの配列を合併(マージ)して、整列された配列を作るのは比較的簡単です。
マージソートは、これを利用して、配列をソートする手法です。

簡単にその手順を示します。

1. データを2分割する。
2. 各々をソートする (再帰的にこの手順を適用する)
3. 2つのソート済みのデータ列をマージする。

手順2で、再帰的にこの処理を適用するわけですが、分割した後の要素が 1個ならば、
整列済みとなるので、再帰的な適用は行いません。

このマージソートは、非常に速度が安定しており、最悪計算量が、O(n log n)です。

整列データに対し、インデックスを指定してランダムにアクセスする必要がないのが特徴です。
そのため、ここでは、IEnumerable&amp<T> を受け取り、IEnumerable<T>を返すSortメソッドを
書いてみました。

コード(後述)を見ていただければわかりますが、MergeSort.Sortメソッドがとても簡潔なのがお分かりに
なると思います。
その下位ルーチンである、2つのソート済みシーケンスをマージするロジックの方が複雑な
アルゴリズムだというのが何ともですね。

なお、初期バージョンでは、マージをするMergerメソッドも、再帰で書いてみたのですが、
とても遅く使い物にならなかったので、ループ処理に書き換えています。
再帰版のコードは、最後に示しています。
再帰処理だから遅いというよりも、LINQの使い方の問題だと思います。
途中結果をToList()メソッドで List<T>に変換することで、速度は改善できることは確認済みです。

以下に、C#のコードを示します。


■Program.cs


■MergeSort.cs
 

■再帰版のMergeメソッド