#include "base.h"

void Merge(RedType SR[],RedType TR[],int i,int m,int n)
{//將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n]
	int j,k;
	int a,b;
	
	for(j=m+1,k=i;i<=m&&j<=n;k++)			//將SR中記錄由小到大地并入TR
	{
		if(LT(SR[i].key,SR[j].key))
		{
			TR[k]=SR[i];
			i++;
		}
		else
		{
			TR[k]=SR[j];
			j++;
		}
	}
	if(i<=m)								//將剩余的SR[i..m]復制到TR
	{
		for(a=k,b=i;a<=n&&b<=m;a++,b++)
			TR[a]=SR[b];
	}
	if(j<=n)								//將剩余的SR[j..n]復制到TR
	{
		for(a=k,b=j;a<=n&&b<=n;a++,b++)
			TR[a]=SR[b];
	}
}

void MSort(RedType SR[],RedType TR1[],int s,int t)
{//將SR[i..t]歸并排序為TR1[s..t]
	int m;
	RedType *TR2;
	TR2=new RedType[MAXSIZE+1];

	if(s==t)
		TR1[s]=SR[s];
	else
	{
		m=(s+t)/2;						//將SR[s..t]平分為SR[s..m]和SR[m+1..t]
		MSort(SR,TR2,s,m);				//遞歸地將SR[s..m]歸并為有序的TR2[s..m]
		MSort(SR,TR2,m+1,t);			//遞歸地將SR[m+1..t]歸并為有序的TR2[m+1..t]
		Merge(TR2,TR1,s,m,t);			//將TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t]
	}
	delete []TR2;
}

void MergeSort(SqList &L)
{//歸并排序
	MSort(L.r,L.r,1,L.length);
}