//二路歸并
//算法思想:設(shè)數(shù)組a中存放了n個(gè)數(shù)據(jù)元素,初始時(shí)把它們看成是n個(gè)長(zhǎng)度為1的有序子數(shù)組，然后從第一個(gè)子數(shù)組開(kāi)始,把相鄰的子數(shù)組兩兩合并，
//得到n/2的整數(shù)上界個(gè)長(zhǎng)度為2的新的有序子數(shù)組(當(dāng)n為基數(shù)時(shí)最后一個(gè)新的有序子數(shù)組的長(zhǎng)度為1);對(duì)這些新的有序子數(shù)組再兩兩歸并；
//如此重復(fù)，直到得到一個(gè)長(zhǎng)度為n的有序數(shù)組為止。多于二路的歸并排序方法的二路歸并排序方法類同
//算法實(shí)現(xiàn):


//一次二路歸并排序算法如下:
void Merge(DataType a[],int n,DataType swap[],int k)
//k為有序子數(shù)組的長(zhǎng)度，一次二路歸并排序后的有序子序列存于數(shù)組swap中
{
	int m=0,u1,l2,i,j,u2;
	int l1=0;			//第一個(gè)有序子數(shù)組下界為0
	while(l1+k<=n-1)
	{
		l2=l1+k;						//計(jì)算第二個(gè)有序子數(shù)組下界
		u1=l2-1;						//計(jì)算第一個(gè)有序子數(shù)組上界
		u2=(l2+k-1<=n-1)?l2+k-1:n-1;	//計(jì)算第二個(gè)有序字?jǐn)?shù)組上界	

		//兩個(gè)有序字?jǐn)?shù)組合并
		for(i=l1,j=l2;i<=u1&&j<=u2;m++)
		{
			if(a[i].key<=a[j].key)
			{
				swap[m]=a[i];
				i++;
			}
			else
			{
				swap[m]=a[j];
				j++;
			}
		}

		
		//子數(shù)組2已歸并完，將子數(shù)組1中剩余的元素存放到數(shù)組swap中
		while(i<=u1)
		{
			swap[m]=a[i];
			m++;
			i++;
		}

		//子數(shù)組1已歸并畢,將自數(shù)組2中剩余的元素存放到數(shù)組swap中
		while(j<=u2)
		{
			swap[m]=a[j];
			m++;
			j++;
		}

		l1=u2+1;
	}

	//將原始數(shù)組中只夠一組的數(shù)據(jù)元素順序存放到數(shù)組swap中
	for(i=l1;i<n;i++,m++)
	{
		swap[m]=a[i];
	}

}


//二路歸并算法如下:
void MergeSort(DataType a[],int n)
{
	int i,k=1;				//歸并長(zhǎng)度從1開(kāi)始
	DataType *swap=new DataType[n];				//申請(qǐng)動(dòng)態(tài)數(shù)組空間

	while(k<n)
	{
		Merge(a,n,swap,k);			//調(diào)用歸并函數(shù)Merge(a,n,swap,k)
		for(i=0;i<n;i++)
		{
			a[i]=swap[i];			//將元素從臨時(shí)數(shù)組swap放回?cái)?shù)組a中
		}
		k*=2;						//歸并長(zhǎng)度加倍
	}
	delete [] swap;					//釋放動(dòng)態(tài)數(shù)組空間
}