/*
     归并排序实现
    coder:QPZ
        time：2014-12-03
*/
#include <time.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
class Mergesort{
       private:
              int *Arr;
              int n;
   public:
           Mergesort(int n){
                  this->n=n;
                  srand((unsigned)time(NULL));
                  Arr=(int*)malloc(n*sizeof(int));
                  for(inti=0;i < n;i++){
                         Arr[i]=rand()%100;
                  }/*endfor*/
           }
     void    Msort(int left,int right);
     void Merge(int left,int right,int rigntEnd);
           void PrinArr();
           ~Mergesort(){
                  free(Arr);
                     }
};
int main(void)
{
       intn;
       cin>>n;
       classMergesort *p=new Mergesort(n);
       p->PrinArr();
       p->Msort(0,n-1);
       p->PrinArr();
       return0;
}
void Mergesort::PrinArr()
{
       for(inti=0;i<n;i++){
              cout<<Arr[i]<<" ";
       }/*endfor*/
       cout<<endl;
}
void Mergesort::Msort(int left,int right){
       intmiddle;
       if(left<right){
              middle=(left+right)/2;
              //分割数集
              Msort(left,middle);
              Msort(middle+1,right);
              //归并操作
              Merge(left,middle+1,right);
       }
}
void Mergesort::Merge(int left,int right,intrightEnd)
{    
       int*TmpArry=(int *)malloc((rightEnd-left+1)*sizeof(int));
       inttmp;
       inti;
       intLeft=left;
       intRight=right;
       /*比大小赋值，结束后接*/
       for(tmp=0;Left<right&& Right<=rightEnd;) {
              if(Arr[Left]<=Arr[Right]){
                     TmpArry[tmp++]=Arr[Left++];
              } else{
                     TmpArry[tmp++]=Arr[Right++];
              }/*end if else*/
       }/*endfor*/
       while(Left<right){
       TmpArry[tmp++]=Arr[Left++];          
       }
       while(Right<rightEnd){
              TmpArry[tmp++]=Arr[Right++];
       }
       /*Tmp赋值返回*/
       for(i=0,Left=left;i< tmp;i++){
              Arr[Left++]=TmpArry[i];
       }/*end for*/
       free(TmpArry);
}