int n;
int *a;

void enter()
{
    srand(time(0));
    cin>>n;
    a=new int[n];
    for(int i=0;i<n-1;i++) a[i]=rand()%100;
}

template <typename T>
void mergeSort(T *pD,int N)
{
    if (N<2) return;
    mergeSort(pD,N/2);
    mergeSort(pD+N/2,N-N/2);
    T *pT=new T[N/2];
    memcpy(pT,pD,sizeof(T)*(N/2));
    int p1Idx,p2Idx,pI;
    p1Idx=pI=0;
    p2Idx=N/2;
    while (1)
    {
        if (pT[p1Idx]<pD[p2Idx]) pD[pI++]=pT[p1Idx++];
        else pD[pI++]=pD[p2Idx++];
        if (p1Idx>=N/2||p2Idx>=N) break;
    }
    while (p1Idx<N/2) pD[pI++]=pT[p1Idx++];
}

template <typename T>
void shellSort(T *a,int n)
{
    int j,temp;
    for(int gap=n/2;gap>0;gap/=2)
    {
        for(int i=gap;i<n;i++)
        {
            j=i;
            temp=a[i];
            for(j=i;j>=gap&&a[j-gap]>temp;j-=gap) a[j]=a[j-gap];
            a[j]=temp;
        }
    }
}

void solveMerge()
{
    clock_t begin,end;
    begin=clock();
    mergeSort(a,n);
    end=clock();
    cout<<"Merge sort time: "<<(double(end-begin))/1000.0<<'n';
}

void solveShell()
{
    clock_t begin,end;
    begin=clock();
    shellSort(a,n);
    end=clock();
    cout<<"Shell sort time: "<<(double(end-begin))/1000.0<<'n';
}

int main()
{
    enter();
    solveMerge();
    solveShell();
}