数据结构---------归并排序

1.思想：归并排序的思想就是分治的思想，它的基本操作就是合并两个已排序好的表A和B，遍历两个表将其排序后输出到表C（数组）。

图示：

那么我们如何用一个非顺序的数组进行排序呢？

2.方法描述：如果N=1，那么只有一个元素被排序，否则，递归的将前半不问数据和后半部分数据各自归并排序，得到排序后的两部分数据，然后使用上面描述的合并算法将这两部分合并到一起。

3.实现：我们使用一个Merge函数进行合并，一个MSort函数进行递归执行。如果我们在Merge历程中每次调用都动态的创建一个数组，malloc会占用很多时间，由于Merge位于MSort的的最后一行，因此任意时刻只需要一个临时数组活动，而且可以使用该临时数组的任意部分即没有重复使用TempArray的任一部分。

代码实现：

合并函数

void Merge(ElementType A[], ElementType TmpArray[], int Lpos, int Rpos, int RightEnd){	int i, LeftEnd, NumElements, TmpPos;	LeftEnd = Rpos - 1;	TmpPos = Lpos;	//使得TempArray的起点与A同步,避免了重复使用TempArray的部分	NumElements = RightEnd - Lpos + 1;	while (Lpos <= LeftEnd && Rpos <= RightEnd)	{		if (A[Lpos] < A[Rpos])			TmpArray[TmpPos++] = A[Lpos++];		else			TmpArray[TmpPos++] = A[Rpos++];	}	while (Lpos <= LeftEnd)		TmpArray[TmpPos++] = A[Lpos++];	while (Rpos <= RightEnd)		TmpArray[TmpPos++] = A[Rpos++];	for (i = 0; i < NumElements; i++, RightEnd--)		A[RightEnd] = TmpArray[RightEnd];} 排序函数
void MSort(ElementType A[], ElementType TmpArray[], int Left, int Right){	int Center;	if (Left < Right)	{		Center = (Left + Right) / 2;		MSort1(A, TmpArray, Left, Center);		MSort1(A, TmpArray, Center + 1, Right);		Merge1(A, TmpArray, Left, Center + 1, Right);	}}4.分析：归并排序的运行时间时O（NlogN），但是它很难用于主存排序，问题在于合并两个排序需要线性附加内存，而且还进行了许多拷贝工作，严重放慢了排序速度。