#include<iostream>
using namespace std;
#define MAX 10000
int array[MAX];  //待排序数组
const int MAXN=0x7fffffff;

void Merge(int array[],int start, int mid, int end) 
{
    int b[MAX],c[MAX],k,i,j;
    int n1=mid-start+1;
    int n2=end-mid;
    
    for (i=0;i<n1;i++)    //copy前半部分
        b[i] = array[start+i];
    for (i=0;i<n2;i++)    //cpoy后半部分
        c[i]=array[mid+i+1];
    
    
    b[n1]=c[n2]=MAXN;
    for (k=start,i=0,j=0;k<=end;k++)
    {
        if (b[i]<=c[j])
        {
            array[k]=b[i];
            i++;
        }
        else
        {
            array[k]=c[j];
            j++;
        }
    }
}

// 归并排序
void MergeSort(int array[],int start, int end)
{
    if(start<end)
    {
        int i=(end+start)/2;
        MergeSort(array,start,i); 
        MergeSort(array,i+1,end); 
        Merge(array,start,i,end);  // 合并前后两部分
    }
}

int main()
{
    int i,n;
    cout<<"数组元素个数：";
    cin>>n;

    cout<<"数组元素值："<<endl;
    for(i=0;i<n;i++) 
         cin>>array[i];

    MergeSort(array,0,n-1);

    cout<<"排序后："<<endl;
    for(i=0;i<n;i++)
        cout<<array[i]<<" ";
    cout<<endl;

    return 0;
}