void _MergeSort(int* arr, int begin, int end, int* tmp)
{
  if (begin >= end)
  {
    return;
  }
  int mid = (begin + end) / 2;
  _MergeSort(arr, begin, mid , tmp);
  _MergeSort(arr, mid + 1, end, tmp);
  int i = begin;
  int begin1 = begin, end1 = mid;
  int begin2 = mid + 1, end2 = end;
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (arr[begin1] <= arr[begin2])//等于时我们取前一个，保证算法的稳定性
    {
      tmp[i++] = arr[begin1++];
    }
    else
    {
      tmp[i++] = arr[begin2++];
    }
  }
  while (begin1 <= end1)
  {
    tmp[i++] = arr[begin1++];
  }
  while (begin2 <= end2)
  {
    tmp[i++] = arr[begin2++];
  }
  memcpy(arr+begin, tmp+begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* arr, int begin, int end)
{
  int* tmp = (int*)malloc(sizeof(int) * (end - begin));
  _MergeSort(arr, begin, end-1, tmp);
  free(tmp);
  tmp = NULL;
}

//写法一：
void MergeSortNonR(int* arr, int n)//栈和队列进行非递归都非常不好搞
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  //rangeN代表归并的每组数据个数，从1开始，因为一个数认为是有序的，可以直接进行归并。
  int rangeN = 1;
  while (rangeN < n)
  {
    for (int i = 0; i < n; i += 2 * rangeN)
    {
      //这里面要实现两个组数据的归并
      // [begin1,end1][begin2,end2] 归并
      int begin1 = i, end1 = i + rangeN - 1;//归并区间1
      int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;//归并区间2，加上2倍的rangeN之后，就跳到下一组了，-1正好就是本组的最后一个元素
      printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
      int j = i;
      //end1 begin2 end2越界
      if (end1 >= n)
      {
        //修正区间  ->拷贝数据可以整体拷贝，也可以归并每组拷贝，因为无论哪种，tmp中的数据不会存在随机值的情况
        end1 = n - 1;
        //让第一个区间修正成一个正确的区间
        //将第二个区间修正成一个不存在的区间。
        begin2 = n;
        end2 = n - 1;
      }
      else if (begin2 >= n)
      {
        //修正成不存在的区间
        begin2 = n;
        end2 = n - 1;
      }
      else if (end2 >= n)
      {
        end2 = n - 1;
      }
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (arr[begin1] <= arr[begin2])//加个等号，遇到相同数字，取前一个。
        {
          tmp[j++] = arr[begin1++];
        }
        else
        {
          tmp[j++] = arr[begin2++];
        }
      }
      while (begin1 <= end1)
      {
        tmp[j++] = arr[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[j++] = arr[begin2++];
      }
      //强烈推荐归并一点，我们就往原数组拷贝回去一点，别一次性就全都拷贝回去
      memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
      //拷贝的个数是2*rangeN是不可以的，因为数据有可能不是恰好分成整数个组，我们有时可能只拷贝一个数据。
    }
    //也可以整体归并完了，再统一将tmp数组拷贝回arr里。
    //memcpy(arr, tmp, sizeof(int) * n);//这就是整体拷贝。
    rangeN *= 2;
  }
  free(tmp);//防止内存泄露
  tmp = NULL;
}
//rangeN是归并的每组的数据个数，然后我们两两为一组，进行归并。
//然后我们每次让range扩大二倍，最后的两组进行归并，结束后，我们就可以得到一个完整的归并序列了。
//先前有问题的逻辑：
//但到了10个测试数据的时候，由于他不是2的n次方个，无法被两两分成一个归并组，出现越界访问。例如rangeN==2时，两两分为一组，肯定有两个
//数据被落下，无法和其他数据凑成一个归并组。除了这样的情况之外，还有很多其他的越界情况，我们需要一一分析
//如果你是修正了区间，以防越界访问的话，那既可以整体拷贝，也可以部分拷贝。
//如果你遇到越界访问，选择跳出归并循环的话，那就不可以整体拷贝，只能部分拷贝。
//写法二：
void MergeSortNonR(int* arr, int n)//栈和队列进行非递归都非常不好搞
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  //rangeN代表归并的每组数据个数，从1开始，因为一个数认为是有序的，可以直接进行归并。
  int rangeN = 1;
  while (rangeN < n)
  {
    for (int i = 0; i < n; i += 2 * rangeN)
    {
      //这里面要实现两个组数据的归并
      // [begin1,end1][begin2,end2] 归并
      int begin1 = i, end1 = i + rangeN - 1;//归并区间1
      int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;//归并区间2，加上2倍的rangeN之后，就跳到下一组了，-1正好就是本组的最后一个元素
      printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
      int j = i;
      //end1 begin2 end2越界
      if (end1 >= n)
      {
        //如果你不修正直接走break，那你是不能整体拷贝的，因为tmp中有一部分值会是随机值，
        break;
      }
      else if (begin2 >= n)
      {
        break;
      }
      else if (end2 >= n)
      {
        end2 = n - 1;//对end2进行修正
      }
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (arr[begin1] <= arr[begin2])//加个等号，保证归并排序是稳定的，遇到相同数字，我们取前一个
        {
          tmp[j++] = arr[begin1++];
        }
        else
        {
          tmp[j++] = arr[begin2++];
        }
      }
      while (begin1 <= end1)
      {
        tmp[j++] = arr[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[j++] = arr[begin2++];
      }
      memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
      //拷贝的个数是2*rangeN是不可以的，因为数据有可能不是恰好分成整数个组，我们有时可能只拷贝一个数据。
    }
    rangeN *= 2;
  }
  free(tmp);//防止内存泄露
  tmp = NULL;
}

void CountSort(int* arr, int n)
{
  int max = arr[0], min = arr[0];
  for (int i = 0; i < n; i++)
  {
    if (arr[i] > max)
    {
      max = arr[i];
    }
    if(arr[i]<min)
    {
      min = arr[i];
    }
  }
  int range = max - min + 1;//[0,2]左闭右闭的情况下，数据的个数一定是要+1的。如果是开区间自然不用，(0,2]数据个数为2。
  //统计次数
  int* countA = (int*)calloc(range, sizeof(int));
  if (countA == NULL)
  {
    perror("malloc fail\n");
    exit(-1);
  }
  for (int i = 0; i < n; i++)//再次遍历arr数组，统计其中数据出现的次数
  {
    countA[arr[i] - min]++;//这里就统计出数据出现的次数了
  }
  //遍历统计次数的数组，对原数组进行计数排序
  int j = 0;
  for (int i = 0; i < range; i++)
  {
    while (countA[i]--)//n--走n次，--n走n-1次。
    {
      arr[j++] = i + min;
      //这里又犯了一个严重的错误，利用了循环变量i，可千万不敢用循环变量i啊，要不然循环的情况就被你改了，代码又出问题了，你妹的。
    }
  }
  free(countA);
  countA = NULL;
}
//时间复杂度：O(N+range)，虽然有两层循环嵌套在一起，但不是×的关系，其实是加的关系。
//空间复杂度：O(range)
//适合数据范围集中，也就是range小
//只适合整型数据的排序，不适合浮点数、字符串等类型。
//如果数据较为集中的话，计数排序还是非常牛逼的，因为N大于range的话，我们的时间复杂度就是O(N)，老天爷，这性能不妥妥的很强么。