はなちるのマイノート

Unityをメインとした技術ブログ。自分らしくまったりやっていきたいと思いますー!

【C#】マージソートを実装してみる

はじめに

今回はマージソートを実装してみようという記事になります!
ja.wikipedia.org

前置きはなしに本題をみていきたいと思います。

マージソート

英語ですが、この動画がすごく分かりやすく説明されていたのでオススメです。
www.youtube.com

実装

public class MergeSort<T> where T : IComparable<T>
{
    public static T[] Excuse(IEnumerable<T> items)
    {
        var nums = items.ToArray();
        return Excuse(nums, 0, nums.Length);
    }

    // 区間[begin, end)
    private static T[] Excuse(T[] nums, int begin, int end)
    {
        if (begin + 1 == end) return new T[] { nums[begin] };

        int mid = (begin + end) / 2;
        var arrayOne = Excuse(nums, begin, mid);
        var arrayTwo = Excuse(nums, mid, end);
        var mergedArray = Merge(arrayOne, arrayTwo);

        return mergedArray;
    }

    private static T[] Merge(T[] a, T[] b)
    {
        int i = 0;          // aの操作する添字
        int j = 0;          // bの操作する添字
        var mergedArray = new T[a.Length + b.Length];
        int index = 0;      // マージ後の操作する添字

        // 小さい方からマージ後の配列に入れていく
        while (i < a.Length && j < b.Length)
        {
            if(a[i].CompareTo(b[j]) < 0)
            {
                mergedArray[index] = a[i];
                i++;
                index++;
            }
            else
            {
                mergedArray[index] = b[j];
                j++;
                index++;
            }
        }

        // 余った配列を入れていく
        for (; i < a.Length; i++, index++) mergedArray[index] = a[i];
        for (; j < b.Length; j++, index++) mergedArray[index] = b[j];

        return mergedArray;
    }
}

使い方

使い方はこんな感じ。

static void Main(string[] args)
{
    var a = new int[] { 170, 45, 75, 90, 2, 24, 802, 66 };

    foreach (var item in MergeSort<int>.Excuse(a))
        Console.WriteLine(item);       // 2, 24, 45, 66, 75, 90, 170, 802
}

考察

最悪計算時間はo(n log n)となることが知られています。

詳細はこちらの資料が分かりやすかったです。
http://www.dais.is.tohoku.ac.jp/~shioura/teaching/ad11/ad11-02.pdf

ざっくりと説明させていただくと,「T(n) = n 個の要素のソートの時間」と仮定した場合以下の再帰方程式が成り立ちます。

T(n) = 2T(n / 2) + cn

右辺のcnは長さn / 2の2つの部分配列への分解・それらが整列された後に併合するのに必要な手間です。

この再帰方程式を解くと T(n) = cn log_2nであることが分かり,最悪計算量はo(n log n)と導けます。