マージソートをC#で実装してみた #C#

マージソートとは

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

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

データを2分割する。
各々をソートする（再帰的にこの手順自身を適用する）
2つのソート済みのデータ列をマージする。

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

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

また、整列データに対し、インデックスを指定してランダムにアクセスする必要がないのが特徴です。

アルゴリズムの勉強のために、このマージソートをC#で書いてみました。

最初に書いたコード

以下、最初に書いたコードです。

Sortメソッドは、汎用性を持たせるため、IEnumerable&amp<T> を受け取り、IEnumerable<T>を返す仕様としました。

後述のコードを見ていただければわかりますが、MergeSort.Sortメソッドがとても簡潔なのがお分かりになると思います。

その下位ルーチンである、２つのソート済みシーケンスをマージするロジックの方が、複雑なアルゴリズムだというのがその簡潔さを物語っていますね。

using System;
using System.Linq;
using System.Collections.Generic;

namespace MergeSortApp {
    static class MargeSort {
        public static IEnumerable<T> Sort<T>(IEnumerable<T> items, Comparison<T> compare) {
            if (items.Count() > 1) {
                int m = items.Count() / 2;
                var a1 = items.Take(m).ToArray();
                var a2 = items.Skip(m).ToArray();
                return Merge(Sort(a1, compare), Sort(a2, compare), compare);
            }
            return items;
        }

        // 再帰版　Mergeメソッド
        private static IEnumerable<T> Merge<T>(IEnumerable<T> a1, IEnumerable<T> a2, Comparison<T> compare) {
            if (!a1.Any()) {
                return a2;
            } else if (!a2.Any()) {
                return a1;
            }
            var x1 = a1.First();
            var x2 = a2.First();
            if (compare(x1, x2) < 0) {
                return (new T[] { x1 }).Concat(Merge(a1.Skip(1), a2, compare));
            } else {
                return (new T[] { x2 }).Concat(Merge(a1, a2.Skip(1), compare));
            }
        }
    }
}

しかし、このプログラムは、LINQの遅延実行の関係でものすごく遅いです。使い物になりません。

ということで以下のように途中で、ToArray()を呼び出すように、書き換えました。これで速くなりました。

    if (compare(x1, x2) < 0) {
        return (new T[] { x1 }).Concat(Merge2(a1.Skip(1), a2, compare)).ToArray();
    } else {
        return (new T[] { x2 }).Concat(Merge2(a1, a2.Skip(1), compare)).ToArray();
    }

速くなったのはいいんですが、このMergeメソッド、ソートする要素数を多くして(7000個程度)動かしてみたら、途中でスタックオーバーを起こしてしまいました。

なかなかいいコードだと思ったんだけどな...

改善したコード

ということで、Mergeメソッドの再帰処理はあきらめて、ループ処理に書き換えることにしました。Sortメソッドは再帰処理のままです。

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

using System;
using System.Linq;
using System.Collections.Generic;

namespace MergeSortApp {
    static class MargeSort {
        public static IEnumerable<T> Sort<T>(IEnumerable<T> items, Comparison<T> compare) {
            if (items.Count() > 1) {
                int m = items.Count() / 2;
                var a1 = items.Take(m).ToArray();
                var a2 = items.Skip(m).ToArray();
                return Merge(Sort(a1, compare), Sort(a2, compare), compare);
            }
            return items;
        }

        // 非再帰版　Mergeメソッド
        private static IEnumerable<T> Merge<T>(IEnumerable<T> a1, IEnumerable<T> a2, Comparison<T> compare) {
            var ite1 = a1.GetEnumerator();
            var ite2 = a2.GetEnumerator();
            var exists1 = ite1.MoveNext();
            var exists2 = ite2.MoveNext();
            while (exists1 == true && exists2 == true) {
                T x1 = ite1.Current;
                T x2 = ite2.Current;
                if (compare(x1, x2) < 0) {
                    yield return x1;
                    exists1 = ite1.MoveNext();
                } else {
                    yield return x2;
                    exists2 = ite2.MoveNext();
                }
            }
            while (exists1) {
                yield return ite1.Current;
                exists1 = ite1.MoveNext();
            }
            while (exists2) {
                yield return ite2.Current;
                exists2 = ite2.MoveNext();
            }
        }
    }
}

Mergeメソッドは、随分と複雑になってしまいましたが、背に腹はかえられません。

これでスタックオーバーは回避できました。速度もさらに速くなりました。
すみません、正確に計測してません m(_ _)m

ところで、MoveNextとCurrentって、普段あまり使わないので、どっちから先に呼び出したら良いのか、わからなくなるんですよね。僕だけでしょうか？

MergeSortクラスの動作を検証するコード

最後に、このクラスの動作を検証するために書いたコードを示します。

using System;
using System.Collections.Generic;
using System.Linq;

namespace MergeSortApp {
    // MergeSortの検証用コード
    class Program {
        static void Main(string[] args) {
            Random rnd = new Random();
            var nums = new int[10000];
            for (int count = 0; count < 10; count++) {
                for (int i = 0; i < nums.Length; i++) {
                    nums[i] = rnd.Next(1, 10000);
                }

                var result = MargeSort.Sort(nums, (a, b) => a - b);
                // LINQのOrderByメソッドの結果と比較することで、MergeSortが正しく整列されているかを確認している
                bool isEqual = Enumerable.SequenceEqual(result, nums.OrderBy(n => n));
                Console.WriteLine(isEqual);
            }
            Console.ReadLine();
        }
    }
}

LINQのOrderByでソートした結果とマージソートで並び替えた結果をEnumerable.SequenceEqualを使って比較しています。

この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。