namespace Merge
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                Console.WriteLine("请选择：");
                Console.WriteLine("1.归并排序（非递归）");
                Console.WriteLine("2.归并排序（递归）");
                Console.WriteLine("3.归并排序（自然合并）");
                Console.WriteLine("4.退出");
                int Arraynum = Convert.ToInt32(Console.ReadLine());
                switch (Arraynum)
                {
                    case 4:
                        Environment.Exit(0);
                        break;
                    case 1:
                        Console.WriteLine("Please Input Array Length");
                        int Leng271 = Convert.ToInt32(Console.ReadLine());
                        Function obj1 = new Function(Leng271);

                        Console.WriteLine("The original sequence:");
                        Console.WriteLine(obj1);
                        Console.WriteLine("'MergeSort' Finaly Sorting Result:");
                        obj1.ToMergeSort();
                        Console.WriteLine(obj1);
                        break;
                    case 2:
                        Console.WriteLine("Please Input Array Length");
                        int Leng272 = Convert.ToInt32(Console.ReadLine());
                        Function obj2 = new Function(Leng272);

                        Console.WriteLine("The original sequence:");
                        Console.WriteLine(obj2);
                        Console.WriteLine("'RecursiveMergeSort' Finaly Sorting Result:");
                        obj2.ToRecursiveMergeSort();
                        Console.WriteLine(obj2);
                        break;
                    case 3:
                        Console.WriteLine("Please Input Array Length");
                        int Leng273 = Convert.ToInt32(Console.ReadLine());
                        Function obj3 = new Function(Leng273);

                        Console.WriteLine("The original sequence:");
                        Console.WriteLine(obj3);
                        obj3.ToNaturalMergeSort();
                        Console.WriteLine();Console.WriteLine();
                        Console.WriteLine("'NaturalMergeSort' Finaly Sorting Result:");
                        Console.WriteLine(obj3);
                        break;
                }
            }
        }
    }
}

namespace Merge
{
    // 【example 2.7】//抱歉，实在不知怎么学习英语，语法什么错误之处还请见谅。
    class Function
    {
        private int Groups;
        private int CopyGroups;
        private int mergerows;
        private int[] Array27;
        private static Random ran = new Random();
        public Function(int length)
        {
            Array27 = new int[length];
            for (int i = 0; i < length; i++)
                Array27[i] = /*Convert.ToInt32(Console.ReadLine()); //*/ran.Next(1, 100);
        }
        //选择
        public void ToMergeSort()
        {
            MergeSort(Array27);
        }
        public void ToRecursiveMergeSort()
        {
            RecursiveMergeSort(Array27, 0, Array27.Length - 1);
        }
        public void ToNaturalMergeSort()
        {
            NaturalMergeSort(Array27);
        }

        ///
        /// 归并排序(递归）
        ///    核心思想：（分治）
        ///           将待排序元素（递归直至元素个数为１）分成左右两个大小大致相同的2个子集合，然后，
        ///           分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合． 
        /// 核心算法时间复杂度：  
        ///           T(n)=O(nlogn)
        /// 参考 优秀代码: http://zh.wikipedia.org/wiki/%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F
        ///               http://www.cnblogs.com/mingmingruyuedlut/archive/2011/08/18/2144984.html
        ///
        ///
        ///
        ///
        public void RecursiveMergeSort(int[] Array, int left, int right)
        {
            int middle = (left + right) / 2;

            if (left < right)
            {
                //对前半部分递归拆分
                RecursiveMergeSort(Array, left, middle);
                //对后半部分递归拆分
                RecursiveMergeSort(Array, middle + 1, right);
                MergeOne(Array, left, middle, right);
            }
        }
        public void MergeOne(int[] Array, int left, int middle, int right)
        {
            int leftindex = left;
            int rightindex = middle + 1;
            //动态临时二维数组存放分割为两个小Array的数组排列顺序后的数据
            int[] merge = new int[right + 1];
            int index = 0;
            //对两个小数组合并排序
            while (leftindex