//****************************************************************************//
//                    Compare QuickSort with MergeSort                          //
//****************************************************************************//

#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream.h>
#include <sys/types.h>
#include <sys/timeb.h>
#include <string.h>

//as following,you can change 
#define Filein "numberin2.txt"            //filenames
#define FileoutQS "numberoutQuickSort2.txt"
#define FileoutMS "numberoutMergeSort2.txt"
#define N 150000
//2^10=1024,2^12=4096,2^14=16384,2^16=65536 2^18=
//2--255555

//******************Produce Numbers to the file Filein**************************

void producenumber(long n)                //n:how many numbers will be produced
{FILE *fp;
srand((unsigned) time(NULL));
if((fp=fopen(Filein,"w"))==NULL)
    {printf("cannot open File.\n");
    return;
    }
long p;
int num;
for(p=0;p<n;p++)
    { 
    num=rand();
    fprintf(fp,"%d",num);
    fseek(fp,sizeof(num),1);
    }
fclose(fp);
}

//******************Read numbers from file Filein*******************************

void readASCnum(int *a,long n)            //a[]:numbers group;n:how many
{FILE *fp;
if((fp=fopen(Filein,"r"))==NULL)
    {printf("cannot open File.\n");
    return;
    }
long p;
int num;
for(p=0;p<n;p++)
    {
    fscanf(fp,"%d",&num);
    a[p]=num;               //数组赋值
    fseek(fp,sizeof(num),1);
    }
fclose(fp);
}

//**************************write results to the file Fileout*******************
void writeASCnum(int a[],long n,char file[])       //write number a[];n:how many
{FILE *fp;
if((fp=fopen(file,"w"))==NULL)
    {printf("cannot open File.\n");
    return;
    }
{for(long i=0;i<n;i++)
    { 
    fprintf(fp,"%d ",a[i]);
    fseek(fp,sizeof(a[i]),1);
    }
}
fclose(fp);
}

//******************************** QuickSort ********************************
template <class T>
void Swap(T &a,T &b)
{
    T temp=a;a=b;b=temp;
}

template <class T>
long Partition(T a[],long p,long r)       //partion from a[p] to a[r]
{
    long i=p;
    long j=r+1;
    T x=a[p];
    while(1){
        while(a[++i]<x);
        while(a[--j]>x);
        if(i>j)break;
        Swap(a[i],a[j]);
    }
    a[p]=a[j];
    a[j]=x;
    return j;
}

template<class T>
void QuickSort(T a[],long p,long r)        //a[]:numbers;p,r:from a[p] to [r] sort
{
    if(p<r){
        long q=Partition(a,p,r);
        QuickSort(a,p,q-1);//对左半段排序
        QuickSort(a,q+1,r);//对右半段排序
    }
}


//******************************** MergeSort *********************************
template<class T>
void Merge(T c[],T d[],long l,long m,long r)
{//合并c[l:m]和c[m+l:r]到d[l:r]
    long i=l,j=m+1,k=l;
    while ((i<=m)&&(j<=r))
        if(c[i]<=c[j])d[k++]=c[i++];
        else d[k++]=c[j++];
    if(i>m)for(long q=j;q<=r;q++)
        d[k++]=c[q];
    else for(long q=i;q<=m;q++)
        d[k++]=c[q];
}

template<class T>
void MergePass(T x[],T y[],long s,long n)
{   
    long i=0;
    while (i<=n-2*s){
        //合并大小为s的相邻2邻段子数组
        Merge(x,y,i,i+s-1,i+2*s-1);
        i=i+2*s;
    }
    //剩下的元素个数少于2s
    if(i+s<n)Merge(x,y,i,i+s-1,n-1);
    else for (long j=i;j<=n-1;j++)
        y[j]=x[j];
}

template<class T>
void MergeSort(T a[],long n)            //port:a[]:number;n:how many
{
    T *b = new T [n];
    long s = 1;
    while (s<n){
        MergePass(a,b,s,n);
        s+=s;
        MergePass(b,a,s,n);
        s+=s;
    }
}




//********************************** smain ************************* ***********
void smain(long n)
{      int *s=new int[n];
    int t1,t2,t;
    producenumber(n);
cout<<"produce over"<<endl;

readASCnum(s,n);
t1=GetTickCount();
QuickSort(s,0,n-1);
t2=GetTickCount();
t=t2-t1;
cout<<"the time QuickSort costed is :"<< t <<endl;
writeASCnum(s,n,FileoutQS);

readASCnum(s,n);
t1=GetTickCount();
MergeSort(s,n);
t2=GetTickCount();
t=t2-t1;
cout<<"the time MergeSort costed is :"<< t <<endl;
writeASCnum(s,n,FileoutMS);

}

void main()
{   
    smain(N);

}

//*********************************** main end *********************************