递归版本：（空间贼大）
//Menteur_Hxy #include <cstdio> #include <iostream> #include <algorithm> #define ll long long #define f(a,b,c) for(register int a=(b);a<=(c);a++) using namespace std; inline ll rd() { ll x=0,fla=1; char c=' '; while(c<'0' || c>'9') {c=getchar();if(c=='-') fla=-fla;} while(c>='0' && c<='9') x=x*10+c-'0',c=getchar(); return x*fla; } inline void out(ll x){ int a[25],wei=0; if(x<0) putchar('-'),x=-x; for(;x;x/=10) a[++wei]=x%10; if(wei==0){ puts("0"); return;} for(int j=wei;j>=1;--j) putchar('0'+a[j]); putchar(' '); } const int MAX=10010; int n; int a[MAX]; void merge(int *num,int *a,int l,int r) { int i=l,j,k=l,m=(l+r)>>1; for(j=m+1;i<=m && j<=r;k++) if(num[i]<=num[j]) a[k]=num[i++]; else a[k]=num[j++]; while(i<=m) a[k++]=num[i++]; while(j<=r) a[k++]=num[j++]; } void mergesort(int *num,int *a,int l,int r) { if(l==r) a[l]=num[l]; else { int t[MAX],mid=(l+r)>>1; mergesort(num,t,l,mid); mergesort(num,t,mid+1,r); merge(t,a,l,r); } } int main() { n=rd(); f(i,1,n) a[i]=rd(); mergesort(a,a,1,n); f(i,1,n) out(a[i]); return 0; }迭代版本：（比较正常）
//Menteur_Hxy #include <cstdio> #include <iostream> #include <cstdlib> #include <algorithm> #include <cstdlib> #define ll long long #define f(a,b,c) for(register int a=(b);a<=(c);a++) using namespace std; inline ll rd() { ll x=0,fla=1; char c=' '; while(c<'0' || c>'9') {c=getchar();if(c=='-') fla=-fla;} while(c>='0' && c<='9') x=x*10+c-'0',c=getchar(); return x*fla; } inline void out(ll x){ int a[25],wei=0; if(x<0) putchar('-'),x=-x; for(;x;x/=10) a[++wei]=x%10; if(wei==0){ puts("0"); return;} for(int j=wei;j>=1;--j) putchar('0'+a[j]); putchar(' '); } const int MAX=100010; int n; int a[MAX],temp[MAX]; void mergesort(int *num,int l,int r) { int k=0,lmi,rmi,lma,rma; for(int i=1;i<=r-l;i*=2) { for(lmi=l; lmi<=r-i; lmi=rma+1) { lma=lmi+i-1,rmi=lma+1,rma=min(r,rmi+i-1); // out(lmi),out(lma),out(rmi),out(rma);putchar('\n'); while(lmi<=lma && rmi<=rma) if(num[lmi] < num[rmi]) temp[k++]=num[lmi++]; else temp[k++]=num[rmi++]; // out(lmi),out(lma),out(rmi),out(rma);putchar('\n'); while(lmi <= lma) num[--rmi]=num[lma--]; while(k) num[--rmi]=temp[--k]; // ,out(temp[k]); // putchar('\n'); // for(int i=1;i<=n;i++) cout<<num[i]<<" "; // putchar('\n'); } } } int main() { n=rd(); f(i,1,n) a[i]=rd(); mergesort(a,1,n); f(i,1,n) out(a[i]); return 0; }