$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

思路：

1. [L,R]=>[l,mid],[mid+1,R]
2. 递归排序[l,mid]和[mid+1,R]
3. 将两个有序序列归并成一个有序序列

完整代码： $O(nlogn)$

#include<iostream>

using namespace std;

const int N = 100010;

int n,a[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++];

    i=l,j=0;
    while(i<=r) q[i++]=tmp[j++];
}

int main()
{
    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;
}