#ifndef SORT_H
#define SORT_H
template<class EType>
void Merge(EType a[],EType aa[],int n,int low ,int up, int m){
int p=low,q=low+m,r;
for(r=1;r<=n;r++)aa[r]=a[r];
r=low;
while(p<low+m && q<up+1){
while(p<low+m && aa[p]<=aa[q]) a[r++]=aa[p++];
if(p<low+m)while(q<up+1 && aa[q]<aa[p])a[r++]=aa[q++];

}
if(p==low+m) for(;q<=up;q++)a[r++]=aa[q];
if(q=up+1) for(;p<=low+m-1;p++) a[r++]=aa[p];
}

template<class EType>
EType minmum(EType u,EType v)
{if(u<v) return u;
else return v;}

template<class EType>
void MergeSort(EType a[],int n){
int low=1;
int up;
int m=1;
EType *aa;
aa=new EType[n+1];
while(m<n){
up=minmum(low+2*m-1,n);
Merge(a,aa,n,low,up,m);
if(up+m<n)low=up+1;
else{
m*=2;
low=1;
}
}delete [] aa;
}
#endif