手撕排序算法4:归并排序及其非递归版本（上）

> 我们可以类比一下快排的递归版本的思想
> 在那里,我们成功使得key前面的数字都小于key,key后面的数字都大于key
> 那么我们当时在想:怎么才能让整个数组都有序呢?
> 只要让它的左半区间有序,右半区间有序,那么整体不久有序了吗?
> 所以我们进行递归调用,不断缩小区间长度
> 最坏的情况下,当某个对应区间的长度等于1时,该区间必定有序

void _MergeSort(int* a, int left, int right,int* tmp)//一般某个主函数的子函数在前面加上_
{
  if (left >= right)//区间长度为1,则必然有序
  {
    return;
  }
  int mid = (left + right) >> 1;
  //等价于int mid = (left+right)/2;
  //假设[left,mid]  [mid+1,right] 有序,那么我们就可以进行归并了
  //那么如何让左右区间均有序呢?
  //类比递归版本的快排和二叉树的深度优先遍历
  //我们可以这样
  _MergeSort(a, left, mid, tmp);
  _MergeSort(a, mid + 1, right, tmp);
  //此时该小区间已经有序了,那么下面开始归并,也就是将有序序列存放到临时数组中
  int begin1 = left, end1 = mid;
  int begin2 = mid + 1, end2 = right;
  int index = left;
  while (begin1 <= end1 && begin2 <= end2)//左右区间有一个结束那么就结束循环
  {
    if (a[begin1] < a[begin2])
    {
      tmp[index++] = a[begin1++];
    }
    else
    {
      tmp[index++] = a[begin2++];//a[begin1]和a[begin2]相等的时候,放谁进入临时数组都可以
    }
  }
  //虽然我们在这里写了两个循环,但是只会进入其中一个
  while (begin1 <= end1)
  {
    tmp[index++] = a[begin1++];
  }
  while (begin2 <= end2)
  {
    tmp[index++] = a[begin2++];
  }
  //拷贝回去
  int i = 0;
  for (i = left; i <= right; i++)
  {
    a[i] = tmp[i];
  }
  //则该小区间已经有序了,对该小区间的递归调用结束
  //每递归到最后时,区间长度为1,已经有序,无需归并,直接return返回即可
  //当递归开始返回时,随着区间长度的增大,该小区间开始进行归并与拷贝,将该小区间变为有序区间
  //随着递归调用的返回,有序区间的长度开始逐渐增大,直到整个数组均有序为止
}
void MergeSort(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);//tmp:临时数组
  _MergeSort(a, 0, n - 1, tmp);
  free(tmp);
}

void _MergeSort(int* a, int left, int right, int* tmp)
{
  if (left >= right)
  {
    return;
  }
  int mid = (left + right) >> 1;
  _MergeSort(a, left, mid, tmp);
  _MergeSort(a, mid + 1, right, tmp);
  //开始归并
}