#include<iostream>
#include<typeinfo>
#define N 100

using namespace std;

void MergeSort(int *R,int low,int mid,int high){
    //用分治法对R[low..high]进行二路归并排序
    int *R1=new int[high-low+1];
    int i,j,p=0;
    i=low;j=mid+1;
    
    if(!R1) {
    cout<<"空间分配失败";
    return ;}
    
    while(i<=mid&&j<=high){
        R1[p++]=(R[i]<=R[j])?R[i++]:R[j++]; //两子文件非空时取其小者输出到R1[p]上
    }
    while(i<=mid){                         //若第1个子文件非空，则复制剩余记录到R1中
        R1[p++]=R[i++];
    }
    while(j<=high){                        //若第2个子文件非空，则复制剩余记录到R1中
        R1[p++]=R[j++];
    }
    for(p=0,i=low;i<=high;i++,p++){         //归并完成后将结果复制回R[low..high]  
        R[i]=R1[p];
    }
    delete [] R1;
}

void Merge(int *R,int low,int high){
    int mid;
    mid=(low+high)/2;
    if(low<high){
    Merge(R,low,mid);//递归排序[low..mid]
    Merge(R,mid+1,high);//递归排序[mid+1..high]
    MergeSort(R,low,mid,high);//将左边和右边合并成一个有序序列
  }
}

int main()
{
    int n,low,high;
    int R[N];
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>R[i];
    
    low=0; high=n-1;
    Merge(R,low,high);

    for(int i=0;i<n;i++)
    cout<<R[i]<<" ";
    
    return 0;
}

2-路归并排序