归并排序（递归实现）

归并排序思想：

1. 使用递归的方法来分元素
2. 使用临时数组来保存排好序的元素
3. 把临时数组中的元素拷贝给原数组

   #include <iostream>
   
   void Merge(int array[], int start, int n, int end);//前置声明
   //归并排序
   void MergeSort(int array[], int low, int high)
   {
       if (low < high)
       {
           int mid = (low + high) / 2;//将数组array[]平分为array[low...mid]与array[mid+1...high]
           MergeSort(array, low, mid);//通过递归将其归为有序
           MergeSort(array, mid+1, high);//通过递归将其归为有序
           Merge(array, low, mid, high);//将两段有序数组归并为一段有序数组
       }
   }
   void Merge(int array[], int start, int n, int end)
   { 
       int* p = new int[end - start + 1];//创建临时数组存放数据
       int j = n + 1;//第二个有序区间的起始地址
       int k= 0;//新数组的下标起始位置
       int i = start;//第一个有序区间的起始地址
       while (i <= n && j <= end)//条件两段数组都不能超过其范围长度
       {
           //通过从两段数组的开始位置比较元素大小，若前段第一个元素大于后段第一个元素则将较小的复制到新数组中，赋值的元素后移一位。
           //被赋值的数组长度加1；
           if (array[i] <= array[j])
           {
               p[k++] = array[i++];
           }
           else
           {
               p[k++] = array[j++];
           }
       }
       //当两段数组中某一段后面有剩余未比较元素则按顺序放入新数组后端。
       while (i <= n)
       {      
            p[k++] = array[i++];      
       }
       while (j <= end)
       {      
            p[k++] = array[j++];        
       }
       for (int v = 0; v < k; v++)//将临时数组数据复制给原始数组
       {
           array[start+v] = p[v];
       }
       delete[]p;//销毁临时数组
   
   }
   
   int main()
   {
       int ch[] = {3,8,4,16,2,66,0,325,52,468};      
       const int length = sizeof(ch) / sizeof(int);
       for (int i = 0; i < length; ++i)
       {
           std::cout << ch[i] << " ";
       }
       std::cout << std::endl;
       int arr[length] = { 0 };
       MergeSort(ch, 0, length-1);
       for (int i = 0; i < length; ++i)
       {
           std::cout << ch[i] << " ";
       }
       return 0;
   }