#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
void mergeSort(int a[],int n);
void merge(int b[],int,int c[],int,int a[],int);

const int MAX=200;
int a[MAX];
void main()
{
    
    int n;
    cout<<endl<<endl;
    cout<<"****************************归并排序显示***********************"<<endl<<endl<<endl;
    do
    {
        cout<<"请输入待排序列表中元素个数n(1<=n<="<<MAX<<"):";
        cin>>n;
    }while(!(n>=1&&n<=MAX));
    cout<<"请输入"<<n<<"个整数："<<endl;
    int i=0;
    do
    {
        cin>>a[i++];
    }while(i<n);
    if(i>=n) cout<<"你已多输入一部分元素，它们将不会参与排序！"<<endl;
    cout<<endl<<"数组a是："<<endl;
    i=0;
    do
    {
        cout<<setw(6)<<a[i++];
        if(i%10==9) cout<<endl;
    }while(i<n);
    cout<<endl;

    mergeSort(a,n);

    cout<<endl<<endl<<"排序后的数组是："<<endl;
    i=0;
    do
    {
        cout<<setw(6)<<a[i++];
        if (i%10==9) cout<<endl;
    }while(i<n);
    cout<<endl;
}

void mergeSort(int a[],int length)
{
    if(length==1) {}
    else
    {
        int b[MAX];
        int c[MAX];
        for(int i=0;i<floor(length/2);i++) b[i]=a[i];
        for(int j=floor(length/2);j<length;j++)  c[j-int(floor(length/2))]=a[j];
        mergeSort(b,floor(length/2));
        mergeSort(c,ceil(length/2));
        merge(b,floor(length/2),c,ceil(length/2),a,length);
    }    
}

void merge(int b[],int lengthB,int c[],int lengthC,int a[],int lengthA)
{
    int i=0,j=0,k=0;
    while(i<lengthB&&j<lengthC)
    {
        if(b[i]<=c[j])  a[k++]=b[i++];
        else  a[k++]=c[j++];
    }
    if(i=lengthB)
    {
        for(;j<lengthC;j++)  a[k++]=c[j];
    }
    else
    {
        for(;i<lengthB;i++)  a[k++]=b[i];
    }
}