void _MergeSort(int* a, int left, int right,int *ret)
{
  int mid = (left + right) >> 1;
  if (left >= right)
    return;
  _MergeSort(a, left, mid, ret);
  _MergeSort(a, mid + 1, right, ret);
  //归并
  int begin1 = left, end1 = mid;
  int begin2 = mid+1, end2 = right;
  int index = left;
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (a[begin1] < a[begin2])
    {
      ret[index++] = a[begin1++];
    }
    else
    {
      ret[index++] = a[begin2++];
    }
  }
  while (begin1 <= end1)
  {
    ret[index++] = a[begin1++];
  }
  while (begin2 <= end2)
  {
    ret[index++] = a[begin2++];
  }
  for (int i = left; i <= right; i++)
  {
    a[i] = ret[i];
  }
}
//归并排序
void MergeSort(int* a, int n)
{
  int* ret = (int*)calloc(sizeof(int) , n);
  _MergeSort(a, 0, n - 1, ret);
  free(ret);
}

#include<stdio.h>
#include<stdlib.h>
void MergeSort(int*a,int n)
{
    int* ret = (int*)calloc(sizeof(int) , n);
    int gap=1;
    while(gap<n)
    {
        for(int i=0;i<n;i+=2*gap)
        {
            //[i,i+gap-1]  [i+gap,i+2*gap-1]
            int begin1 = i, end1 =i+gap-1;
            int begin2 = i+gap, end2 = i+gap*2-1;
            int index = i;
            //边界的修正
            if(begin2>=n)
                break;
                if(end2>=n)
                end2=n-1;
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (a[begin1] < a[begin2])
                {
                    ret[index++] = a[begin1++];
                }
                else
                {
                    ret[index++] = a[begin2++];
                }
            }
            while (begin1 <= end1)
            {
                ret[index++] = a[begin1++];
            }
            while (begin2 <= end2)
            {
                ret[index++] = a[begin2++];
            }
             for (int j = 0; j<=end2; j++)
            {
                a[j] = ret[j];
            }
            }
         gap*=2;
    }
    free(ret);
}