#include<iostream>
using namespace std;
int merge(int arr[],int begin,int middle,int end);
int mergeSort(int arr[],int begin,int end){
if(end-begin==1){//如果区间中只有两个元素
if(arr[begin]>arr[end]){
int temp=arr[begin];
arr[begin]=arr[end];
arr[end]=temp;
}
return 0;
}
else if(end-begin==0){//区间中只有一个数
return 0;
}
else{//多于两个数则继续划分
int m=(begin+end)/2;
mergeSort(arr,begin,m);
mergeSort(arr,m+1,end);
merge(arr,begin,m,end);
}
}
int merge(int arr[],int begin,int middle,int end){
int help[end-begin+1];//帮助数组,将排好序的数据放入新数组
int i=begin;
int j=middle+1;
int k=begin;
while(i<=middle&&j<=end){
help[k++]=arr[i]<arr[j]?arr[i++]:arr[j++];
}
while(i<=middle)
help[k++]=arr[i++];
while(j<=end)
help[k++]=arr[j++];
for(int i=0;i<k;i++){//将新数组中排好的数传给arr【】
arr[i]=help[i];
}
}
int main(){
int num;
cout<<"输入数组长度:"<<endl;
cin>>num;
int R[num];
cout<<"输入数组数据()";
for(int i=0;i<num;i++){
cin>>R[i];
}
mergeSort(R,0,num);
for(int j=0;j<num;j++)
cout<<R[j]<<" ";
}