#include<iostream.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<stdio.h>

const int n=1000000;

typedef struct{
	int key;
}RedType;

typedef struct{  
RedType  *r;       //r[n+1];
int length;
}SqList;


int random();
void Merge(SqList &R,SqList &R1,int low, int mid,int high);
void MergePass(SqList &R,SqList &R1,int m,int len);
void MergeSort(SqList &R,SqList &R1,int m);
void main(){ 
//	int m;
	//m=log10(double(n+1))/log10(double(2));
  	SqList L;
    SqList L1;
	L.r = new RedType[n+1];
	L1.r=new RedType[n+1];
	L.length=n;
	for(int i=1;i<=n;i++)	L.r[i].key=random();
	long t1,t2;	
	t1=clock();
    MergeSort(L,L1,n);
	t2=clock();
	cout<<" 時(shí)間: "<<float(t2-t1)/CLK_TCK<<endl;
//	for(i=1;i<=n;i++)
//		cout<<L.r[i].key<<endl;
	
	
}
int random(){
    	int A=48271;
	int M=2147483647;
	int Q=M/A;
	int R=M%A;
	static int x=1;	int x1;
	x1=A*(x%Q)-R*(x/Q);
	if(x1>=0) x=x1;
	else	x=x1+M;
	return x;
}

void Merge(SqList &R,SqList &R1,int low, int mid,int high)
{
		int i,j,k;
		i=low;j=mid+1;k=low;
		 while(i<=mid&&j<=high)
    	 if(R.r[i].key<=R.r[j].key)
			R1.r[k++]=R.r[i++];
			else  R1.r[k++]=R.r[j++];
			while(i<=mid) R1.r[k++]=R.r[i++];
			while(j<=high) R1.r[k++]=R.r[j++];
}

void MergePass(SqList &R,SqList &R1,int m,int len){  //對(duì)R做一趟歸并,結(jié)果在R1中
int i,j;
i=1;                                 //i指第一對(duì)子表的起始點(diǎn)
while(i+2*len-1<=m){                  //歸并長(zhǎng)度為len的兩個(gè)子表
Merge(R,R1,i,i+len-1,i+2*len-1);
i=i+2*len;                           //指向下一對(duì)子表起始點(diǎn)
}
if(i+len-1<m)                        //剩下兩個(gè)子表,其中一個(gè)長(zhǎng)度小于len
Merge(R,R1,i,i+len-1,m);
else                               //子表個(gè)數(shù)為奇數(shù),剩一段
for(j=i;j<=m;j++)                    //將最后一個(gè)表復(fù)制到R1中
R1.r[j]=R.r[j];
}


void MergeSort(SqList &R,SqList &R1,int h) {        //對(duì)R二路歸并排序,結(jié)果在R中(非遞歸算法)
int len;
len=1;
while(len<h){
MergePass(R,R1,h,len);len=len*2;         //一趟歸并,結(jié)果在R1中
MergePass(R1,R,h,len);len=len*2;         //再次歸并,結(jié)果在R中

}
}