归并排序的主要是采用的分治的思想，将一个区间不断的二分划分，然后做归并操作
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
void Merge(int* a,int l,int r,int* res){
int len = (r-l)/2 + 1;
int left = l;
int right = l+len;
int res_index = l;
while(left<l+len && right<r+1){
if(a[left] <= a[right]) res[res_index++] = a[left++];
else res[res_index++] = a[right++];
}
while(left<l+len){ res[res_index++] = a[left++]; }
while(right<r+1){ res[res_index++] = a[right++]; }
return;
}
void MergeSort(int *a,int l,int r,int *res){
if(l<r){
int len = (r-l)/2;
MergeSort(a,l,l+len,res);
MergeSort(a,l+len+1,r,res);
Merge(a,l,r,res);
for(int i = l;i<=r;i++)
a[i] = res[i];
}
return;
}
int a[MAXN],res[MAXN];
int main(){
int n;
scanf("%d",&n);
for(int i = 0;i<n;i++)
scanf("%d",&a[i]);
MergeSort(a,0,n-1,res);
for(int i = 0;i<n;i++)
printf("%d ",a[i]);
return 0;
}
