ALDS1_5_B: Merge Sort

問題へのリンク

C#のソース

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

// Q017 マージソート https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("10");
            WillReturn.Add("8 5 9 2 6 3 7 1 10 4");
            //1 2 3 4 5 6 7 8 9 10
            //34
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] SArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();
        MergeSort(SArr, 0, SArr.GetUpperBound(0) + 1);

        Console.WriteLine(string.Join(" ", Array.ConvertAll(SArr, pX => pX.ToString())));
        Console.WriteLine(mCompareCnt);
    }

    static int mCompareCnt = 0;

    static void MergeSort(int[] Arr, int left, int right)
    {
        if (left + 1 < right) {
            int mid = (left + right) / 2;
            MergeSort(Arr, left, mid);
            MergeSort(Arr, mid, right);
            Merge(Arr, left, mid, right);
        }
    }

    static void Merge(int[] Arr, int left, int mid, int right)
    {
        int n1 = mid - left;
        int n2 = right - mid;
        int[] L = new int[n1 + 1];
        int[] R = new int[n2 + 1];
        for (int I = 0; I <= n1 - 1; I++) {
            L[I] = Arr[left + I];
        }
        for (int I = 0; I <= n2 - 1; I++) {
            R[I] = Arr[mid + I];
        }
        L[n1] = int.MaxValue;
        R[n2] = int.MaxValue;

        int LoopI = 0, LoopJ = 0;
        for (int LoopK = left; LoopK <= right - 1; LoopK++) {
            if (L[LoopI] <= R[LoopJ]) {
                Arr[LoopK] = L[LoopI++];
            }
            else {
                Arr[LoopK] = R[LoopJ++];
            }
            mCompareCnt++;
        }
    }
}

解説

疑似コードをC#で実装してます。