归并排序

归并排序的思想就是先拆分，在合并，在合并的时候进行排序
根据拆分的原则，通常是将数组拆分成每两个数据为一组，进行排序之后再进行归并。
拆分思想就要用到递归的性质，不断地将数组分割，直到数组中的数据只有两个时，才开始惊醒排序和归并。

代码

include[HTML_REMOVED]
using namespace std;
const int N=100010;
int q[N],tmp[N];
void merge_sort(int q[],int l,int r){
if (l>=r) return ; //当递归到数组中的数据少于两个时，就进行排序合并
int mid=l+r>>1; //如果不满足，就继续拆分
merge_sort(q,l,mid),merge_sort(q,mid+1,r);
int k=0;i=l;j=mid+1;
while(i<=mid&&j<=r){
if (q[i]<q[j]) tmp[k]=q[i];
else tmp[k]=q[j];

}
while(i<=mid) tmp[k]=q[i];
while(j<=r) tmp[k] =q[j];
for (int i=l,k=0;i<=r;i++){
q[i]=tmp[k];
}
}
int main(){

int n;
scanf("%d",&n);
for (int i=0;i<n;i++) scanf("%d",&q[i]);
merge_sort(q,0,n-1);
for (int i=0;i<n;i++) printf("%d ",q[i]);
return 0;

}

```