归并排序--MergeSort

归并排序思想：递归地将排序的链表从中间分开，前半部分排好序，后半部分排好序，然后将这排好的两部分归并为一个有序数组。
程序划分：1)对外提供一个接口，即MergeSort();函数调用递归处理函数进行处理并排序
2）MSort（）函数对输入链表进行递归排序，递归终止条件是当前无法再分半（即前面指针和后面指针指向同一个地方），需要一个临时数组变量TR2来存放排序后的数据。 在排完序后调用Merge（）进行归并。
3）Merge（）将两个半个排序好的数组，合并到一个原来的数组中（成为升序）

/*BEGING OF THE FIRST KIND OF Merge TSORT,--------归并排序
*/
template<class T>
void Merge(T *SR,T *TR,int start,int middle, int end)
{
	int j,k;
	for( j=middle+1,k=start;start<=middle && j<=end;k++)
	{
		if(SR[start]<=SR[j])
			TR[k]=SR[start++];
		else
			TR[k]=SR[j++];
	}
	if(start<=middle)             //将剩余的SR[i..middle]赋值到TR
		for(int a=start;a<=middle;a++)
			TR[k++]=SR[a];
	else if(j<=end)               //将剩余的SR[middle+1..end]赋值到TR
		for(int b=j;b<=end;b++)
			TR[k++]=SR[b];
	Output3(TR,1,8);
}
template<class T>
void MSort(T *SR,T* TR1,int s,int t)
{
	T TR2[9];  //should adjust the size if needed
	int m; 
	//将 SR[s...t]归并排序为 TR[s...t]
	if(s==t)
	{	TR1[s]=SR[s];
		Output3(TR1,1,8);
	}
	else
	{
		m=(s+t)/2;
		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]
	}
}
template<class T>
void MergeSort(SqList<T> &L)
{
	MSort(L.key,L.key,1,L.length);
}
/*END OF THE FIRST KIND OF Merge SORT,--------归并排序
*/

输入的数据是
134,52,67,768,435,57,78,2