#include <iostream>
#include <stdlib.h>
using namespace std;

template<class T>void mergeSort(T a[],int left,int right);
void printArray(int a[],int n){
    for(int i=0;i<n;i++){
       cout<<a[i]<<"\t";
    }
}

void Merge(int c[],int d[],int l,int m,int r){
   int i=1;
   int j=m+1;
   int k=1;
   while((i<=m)&&(j<=r)){
       if(c[i]<=c[j]){
        d[k++]=c[i++];
       }else{
         d[k++]=c[j++];
       }
   }

   if(i>m){
      for(int q=j;q<=r;q++){
         d[k++]=c[q];
      }
   }else{
      for(int q=i;q<=m;q++){
          d[k++]=c[q];
      }
   }
}

void Copy(int a[],int b[],int left,int right){
    for (int i = left; i < right; ++i)
    {
        a[i]=b[i];
    }
}

void mergeSort(int a[],int left,int right){

    if(left<right){
       int i=(left+right)/2;
       int *b=new int[100];
       mergeSort(a,left,i);
       mergeSort(a,i+1,right);
       Merge(a,b,left,i,right);
       Copy(a,b,left,right);

    }


}


int main(){
   int a[10]={10,3,90,22,8,1,20,100,33,106};
    cout<<"排序前：\n";
    printArray(a,10);
    mergeSort(a,0,9);
    cout<<"排序后：\n";
    printArray(a,10);
}