using System;

 using System.Collections.Generic;

 using System.Linq;

 using System.Text;

 using System.Threading.Tasks;

 namespace ConsolePractice

 {

     class CArray

     {

         private int[] arr;

         //数组大小

         private int upper;

         //下标

         private int numElements;

         /// <summary>

         /// 初始化数组参数

         /// </summary>

         /// <param name="size"></param>

         public CArray(int size)

         {

             arr = new int[size];

             upper = size - ;

             numElements = ;

         }

         /// <summary>

         /// 插入方法

         /// </summary>

         /// <param name="item">存储的数</param>

         public void Insert(int item)

         {

             arr[numElements] = item;

             numElements++;

         }

         /// <summary>

         /// 输出方法

         /// </summary>

         public void DisplayElements()

         {

             for (int i = ; i <= upper; i++)

             {

                 Console.Write(arr[i] + " ");

             }

             Console.WriteLine();

         }

         /// <summary>

         /// 清除数组

         /// </summary>

         public void Clear()

         {

             for (int i = ; i <= upper; i++)

             {

                 arr[i] = ;

             }

             numElements = ;

         }

         #region 递归排序算法

         /// <summary>

         /// 递归排序合并两个子集的方法

         /// </summary>

         /// <param name="tempArray">临时数组</param>

         /// <param name="lowp">子集1的下标</param>

         /// <param name="highp">子集2的下标，同时可以计算出子集1的长度</param>

         /// <param name="ubound">子集2的长度</param>

         public void Merge(int[] tempArray, int lowp, int highp, int ubound)

         {

             //主数组arr的初始下标位置

             int lbound = lowp;

             //子集1的长度

             int mid = highp - ;

             //主数组arr的长度

             int n = (ubound - lbound) + ;

             int j = ;

             //3个while的作用是合并子集1和子集2到临时的数组中

             while ((lowp <= mid) && (highp <= ubound))

             {

                 if (arr[lowp] < arr[highp])

                 {

                     tempArray[j] = arr[lowp];

                     lowp++;

                     j++;

                 }

                 else

                 {

                     tempArray[j] = arr[highp];

                     highp++;

                     j++;

                 }

             }

             //子集1还留有数值时

             while (lowp <= mid)

             {

                 tempArray[j] = arr[lowp];

                 j++;

                 lowp++;

             }

             //子集2还留有数值时

             while (highp <= ubound)

             {

                 tempArray[j] = arr[highp];

                 j++;

                 highp++;

             }

             //将临时数组存储的数值替换主数组的数值。

             for (j = ; j <= n - ; j++)

             {

                 arr[lbound + j] = tempArray[j];

             }

             this.DisplayElements();

         }

         /// <summary>

         /// 递归方法

         /// </summary>

         /// <param name="tempArray">临时数组</param>

         /// <param name="lbound">数组的最小下标</param>

         /// <param name="ubound">数组的最大下标</param>

         public void RecMergeSort(int[] tempArray, int lbound, int ubound)

         {

             if (lbound == ubound)

                 return;

             else

             {

                 //求出中间的下标

                 int mid = (int)(lbound + ubound) / ;

                 //子集1的递归

                 RecMergeSort(tempArray, lbound, mid);

                 //子集2的递归

                 RecMergeSort(tempArray, mid + , ubound);

                 //合并子集1和子集2

                 Merge(tempArray, lbound, mid + , ubound);

             }

         }

         /// <summary>

         /// 调用递归排序算法

         /// </summary>

         public void MergeSort()

         {

             int[] tempArray = new int[numElements];

             RecMergeSort(tempArray,,numElements-);

         }

         #endregion

     }

     class C_shape

     {

         static void Main()

         {

             CArray nums = new CArray();

             Random rnd = new Random();

             for (int i = ; i < ; i++)

             {

                 nums.Insert(rnd.Next(, ));

             }

             Console.WriteLine("Before sorting:");

             nums.DisplayElements();

             Console.WriteLine("During sorting:");

             nums.MergeSort();

             Console.WriteLine("After sorting:");

             nums.DisplayElements();

             Console.ReadKey();

         }

     }

 }