/*歸并排序的C++語言描述*/
#include<iostream.h>
#include<stdlib.h>
#include<windows.h>

#define N 2000

template<class T>void MergeSortL(T A[],T Link[],int low,int high,int &p);
template<class T>void MergeL(int q,int r,int &p);
template<class T>void InsertSort(T A[],T Link[],int low,int high,int &p);

void main()
{
	int const ARRAYLG(1000);//數組長度
	int a[ARRAYLG+1];
	int link[ARRAYLG+1];
	int begin=0;
	a[0]=-1;
	link[0]=0;
	for(int i=1;i<=ARRAYLG;i++)//給數組賦值
	{
		a[i]=rand()%N;
		link[i]=0;
	}
	LARGE_INTEGER litmp;
	LONGLONG QPart1,QPart2;
	double dfMinus,dfFreq,dfTim;
	QueryPerformanceFrequency(&litmp);
	dfFreq=(double)litmp.QuadPart;//獲得計數器的時鐘頻率
	QueryPerformanceCounter(&litmp);
	QPart1=litmp.QuadPart;//獲得初始值

	MergeSortL(a,link,1,ARRAYLG,begin);//排序

	QueryPerformanceCounter(&litmp);
	QPart2=litmp.QuadPart;//獲得中止值
	dfMinus=(double)(QPart2-QPart1);
	dfTim=dfMinus/dfFreq;//獲得對應的時間值，單位為秒
	cout<<"The total time is:"<<dfTim<<" seconds."<<endl;
	/*for(i=0;i<=ARRAYLG;i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
	for(i=0;i<=ARRAYLG;i++)
	{
		cout<<link[i]<<" ";
	}
	cout<<endl;
	*/
}

template<class T>
void MergeSortL(T A[],T Link[],int low,int high,int &p)
/*Link是數組A[low:high]的下標表,p指示這個表的開始處。利用Link將A按非降順序排列*/
{
	if(high-low+1<4)//設定子問題的最小規模
		InsertSort(A,Link,low,high,p);
	else
	{
		int mid=(low+high)/2;
		int q=0;
		MergeSortL(A,Link,low,mid,q);//返回q表
		int r=0;
		MergeSortL(A,Link,mid+1,high,r);//返回r表
		MergeL(A,Link,q,r,p);//將表q和r合并成表p
	}
}

template<class T>
void MergeL(T A[],T Link[],int q,int r,int &p)
/*由鏈接表q和r構造新的連接表p。q,r是數組Link[1:n]中兩個表指針，這兩個鏈表指出被劃分的兩個子組的
地址排序，而p指針指出兩組歸并后的地址排序。實際上都是表的相互順序在變*/
{
	int i=q,j=r,k=0;//定義及初始化，新表在Link[0]處開始
	while(i!=0&&j!=0)//當兩個表皆非空時
	{
		if(A[i]<=A[j])
		{
			Link[k]=i;
			k=i;
			i=Link[i];//加一個新元素到此表
		}
		else
		{
			Link[k]=j;
			k=j;
			j=Link[j];
		}
	}
	if(i==0)
		Link[k]=j;
	else
		Link[k]=i;
	p=Link[0];
}

template<class T>
void InsertSort(T A[],T Link[],int low,int high,int &p)//插入排序算法
{	
	Link[0]=low;
	for(int i=low+1;i<=high;i++)
	{
		T t=A[i];
		int j=0,temp=0;
		for(j=Link[0];j!=0&&t>=A[j];temp=j,j=Link[j])
			;
		if(j!=0)
		{
			Link[i]=j;
			Link[temp]=i;
		}
		else
		{
			Link[temp]=i;
		}
	}
	p=Link[0];
}