算法模板：归并排序

1.确定分界点中间值，将整个区间一分为二
2.递归 两个子区间,直到每个子区间左右的仅有一个元素时开始合并
   因为后面在合并的过程中会将区间排序 
   所以每次递归之后返回的数组区间都是排序好的
3.归并，将左右两个有序序列合并成一个有序序列
   合并方法：双指针
   先创建一个暂时存储答案的temp数组
   同时将放在左右区间的左端点的指针向右移动
   于此同时比较两指针各指向的元素
   将较小的元素放到tmep数组里
   然后较小的元素的指针继续向中间移动
   一位后继续与另一个指针指向的元素比较大小
   再将较小的元素放到tmep数组里
   反复重复这个过程直到某一个区间被全部遍历
   就可以直接将另一个区间的元素按顺序存入到temp数组里面了
   最后在将答案数组复制到原数组中

#include<bits/stdc++.h>
using namespace std;
int a[10000];
void merge_sort(int a[],int l , int r)
{
  if(l>=r)return ;
  int temp[100];
  int mid=l+r>>1;
  int k=0,i=l,j=mid+1;
  merge_sort(a,l,mid);
  merge_sort(a,mid+1,r);
  while(i<=mid&&j<=r)
  if(a[i]<=a[j])
  temp[k++]=a[i++];
  else
  temp[k++]=a[j++];
  while(i<=mid)temp[k++]=a[i++];
  while(j<=r)temp[k++]=a[j++];
  for(int i = l,j = 0 ; i <= r ; i ++, j ++)
  a[i]=temp[j];
}
int main()
{
  int n;
  cin>>n;
  for(int i = 0 ; i < n ; i ++)
  cin>>a[i];
  merge_sort(a,0,n-1);
  for(int i = 0 ; i <  n ; i ++)
  cout<<a[i]<<" ";
  return 0;
}