经典的归并排序写法
#include<iostream>
using namespace std;
int n;
int a[2500];
//归并排序
int b[2500];
int merge(int a[],int start,int end,int b[]);
int merge_sort(int a[],int start,int end,int b[]){
if(start>=end)
return 0;
merge_sort(a,start,(start+end)/2,b);
merge_sort(a,(start+end)/2+1,end,b);
merge(a,start,end,b);
return 0;
}
int merge(int a[],int start,int end,int b[]){
int middle=(start+end)/2;
int rightindex=middle+1;
int leftindex=start;
int index=leftindex;
while(leftindex<=middle&&rightindex<=end){
if(a[leftindex]<a[rightindex]){
b[index++]=a[leftindex++];
}else{
b[index++]=a[rightindex++];
}
}
while(leftindex<=middle){
b[index++]=a[leftindex++];
}
while(rightindex<=end){
b[index++]=a[rightindex++];
}
for(int i=start;i<=end;i++){
a[i]=b[i];
}
return 0;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
int start=0,end=n-1;
merge_sort(a,start,end,b);
for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
return 0;
}