分治的思想，时间复杂度O(nlogn)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXN = 100005;inline int rd(){ int x=0,f=1;char ch=getchar(); while(ch<'0' || ch>'9') { if(ch=='-') f=-1;ch=getchar();} while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f;}int n,a[MAXN],cpy[MAXN];inline void merge_sort(int l,int r){ if(l==r) return; int mid=l+r>>1; merge_sort(l,mid); merge_sort(mid+1,r); int i=l,j=mid+1,k=l; while(i<=mid && j<=r){ if(a[i]<=a[j]) cpy[k++]=a[i++]; else cpy[k++]=a[j++]; } for(i;i<=mid;i++) cpy[k++]=a[i]; for(j;j<=r;j++) cpy[k++]=a[j]; for(register int i=l;i<=r;i++) a[i]=cpy[i];}int main(){ n=rd(); for(register int i=1;i<=n;i++) a[i]=rd(); merge_sort(1,n); for(register int i=1;i<=n;i++) printf("%d ",a[i]); return 0;}