算法思想

1.确定分界点，不断切分成两部分（对于n个数据一共需要切分logn次）（先分后排）
2.递归排序左右两段
3.归并->两段合二为一

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,num[N],temp[N];//temp作为临时操作数组存放处理过的数据 
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;//k为temp起始下标，i为左段起始下标，j为右段起始下标 

    while(i<=mid&&j<=r){//如果左段和右段都没有超过该段下标范围 
        if(q[i]<q[j])temp[k++]=q[i++];//如果左段所指值小于右段，则将左段所指值插入到temp中并将指针向后移一位 
        else temp[k++]=q[j++];//与上一句同理 
    } 
    while(i<=mid)temp[k++]=q[i++];//如果左段还有数据（先小） 
    while(j<=r)temp[k++]=q[j++];//如果右段还有数据 （后大） 
    for(int i=l,j=0;i<=r;i++,j++)q[i]=temp[j];//temp从0开始给被排序的数组下标从左边界开始，到右边界结束进行赋值 
} 
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)scanf("%d",&num[i]);
    merge_sort(num,0,n-1);
    for(int i=0;i<n;i++)printf("%d ",num[i]);
    return 0;
}