归并排序--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
