归并排序算法之改进

归并排序：将一组数组中前后相邻的两个有序序列归并为一个有序序列

核心操作：假设有n个序列，然后两两归并，得到[n/2]个长度为2或者1的子序列；然后再两两归并，……直至得到一个长度为n的有序序列为止，这种排序方法为2路归并排序

看下面一个2路归并算法

int MSort(MergeType S, MergeType *pT, int nStart, int nEnd)
{
	int nMidPos = 0;
	if ( !S.elem || nStart > nEnd)
	{
		return -1;
	}
	
	if (nStart == nEnd)
	{
		pT->elem[nStart] = S.elem[nStart];
		return 0;
	}

	nMidPos = (nStart + nEnd) / 2;
	MSort(S, pT, nStart, nMidPos);
	MSort(S, pT, nMidPos + 1, nEnd);
	Merge(S, pT, nStart, nMidPos, nEnd);

	return 0;
}

上面的步骤是将数据对半分割，直至只有一个数据，然后再进行归并，这是个递归的操作，看一下如何进行归并操作：

/*S:原数据列表，pT:排序好的数据列表，其他数据和函数定义请参考：冒泡算法的改进 */

int Merge(MergeType S, MergeType *pT, int nStart, int nPos, int nEnd)
{
	int nSi = nStart, nSj = nPos + 1;
	int nTi = nStart;

	for ( ; nSi <= nPos && nSj <= nEnd; )
	{   //这里出现错误
		pT->elem[nTi++] = (S.elem[nSi] <= S.elem[nSj]) S.elem[nSi++]:S.elem[nSj++];
	}

	//剩余的数据
	while (nSi <= nPos)
	{
		pT->elem[nTi++] = S.elem[nSi++];
	}

	while (nSj <= nEnd)
	{
		pT->elem[nTi++] = S.elem[nSj++];
	}
	return 0;
}

假设一个数组为（0,10,24） ，另一个为（32,45），这时候（0,10,24）会被填充进数组T中，但是另一个数组（32,45）还没有插入数组T，后面两个while循环，只需将剩余插入数组T尾部，这时候不用进行比较，一定是插在数组的尾部，for循环比较已经知道谁大小了，另外剩余的数组已经排序好了。

表面上看上面的算法是正确的，其实在归并的时候就有问题，已在注释中说明地方，请大家思考如何修正错误？错误不一定就是那里！！