void Merge(DataType a[], int n, DataType swap[], int k)
//k為有序子數組的長度，一次二路歸并排序后的有序子序列存于數組swap中
{
	int m = 0, u1,l2,i,j,u2;

	int l1 = 0;							//第一個有序子數組下界為0
	while(l1+k <= n-1)
	{
		l2 = l1 + k;					//計算第二個有序子數組下界
		u1 = l2 - 1;					//計算第一個有序子數組上界
		u2 = (l2+k-1 <= n-1)? l2+k-1: n-1;//計算第二個有序子數組上界

		//兩個有序子數組合并
		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++;
			}
		}

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

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

		l1 = u2 + 1;
	}

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

void MergeSort(DataType a[], int n)
{
	int i, k = 1;								//歸并長度從1開始
	DataType *swap = new DataType[n];			//申請動態數組空間

	while(k < n)
	{
		Merge(a, n, swap, k);		//調用歸并函數Merge(a, n, swap, k)
		for(i = 0; i < n; i++)	
			a[i] = swap[i]; 		//將元素從臨時數組swap放回數組a中
		k = 2 * k; 								//歸并長度加倍
	}
	delete []swap;								//釋放動態數組空間
}