【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
}