数据结构归并排序

归并排序是建立在归并操作上的一种有效的排序算法，将两个（或两个以上）有序表合并成一个新的有序表。采用分治法，分而治之：分就是将待排序序列分为若干个有序的子序列，每个子序列是有序；合就是把有序的子序列合并为整体有序序列。

这个算法的基本操作是合并两个已排序的表，因为这两个表是已排序的，所以若将输出放到第三个表中时，则该算法可以通过对输入数据一趟排序来完成。将两个有序表合并成一个有序表，成为2-路归并。可知归的前提是子序列是排序好的，我们可以把整体序列递归地分割成一个一个的子序列，当子序列中仅有一个元素时，该子序列自然就是已排序好，然后再不断的进行2-路归并，最终得到整体有序序列。

下面用图演示这一过程

需要说明的是，上面的分割是意识形态的，和前面介绍的堆排序类似，并不是实际的分割，分割过程中，元素在序列中的位置不变，我们仍可以通过数组索引定位元素。

从上面的图解很容易得知，“2-路分割”和 2-路合并，首先需要将整体无序序列进行递归“2-路分割”，直至分割达到有序状态即子序列仅一个元素（这也是递归的终止条件），然后就是合并，将子序列从小到大放入额外暂存单元中，全部归并完毕，这个暂存单元中的元素就是有序的。

/*2-路合并，这里的unsorted[]为输入数组，sorted[]为暂存单元
first表示子序列起始位置，其值为子序列在整体序列中的位置值
last表示子序列的结束位置（最后一个元素的后面那个位置，同STL）
第一路：[first, mid) 第二路：[mid, last)

*/
void Merge(int unsorted[], int first, int mid, int last, int sorted[])
{
	int i = first, j = mid;
	int k = 0;

	while (i < mid && j < last)
	{
		if (unsorted[i] < unsorted[j])
			sorted[k++] = unsorted[i++];
		else
			sorted[k++] = unsorted[j++];
	}
	 
	while (i < mid)
		sorted[k++] = unsorted[i++];
	 
	while (j < last)
		sorted[k++] = unsorted[j++];
	 
	/*2-路合并的结果，与后面一路是无序的(这两路不在同一序列中)，
	需要将前面合并的结果导入输入序列中，再次进行2-路合并,first表征相对位置*/
	for (int v = 0; v < k; ++v)
		unsorted[v + first] = sorted[v];

}

/*分割及归并排序*/
void MergeSort(int unsorted[], int first, int last, int sorted[])
{
	if (first + 1 < last)
	{
		int mid = first + ((last - first) >> 1); //mid=(left+right)>>1;当left和right比较大时，有溢出的危险
		MergeSort(unsorted, first, mid, sorted);
		MergeSort(unsorted, mid, last, sorted);
		Merge(unsorted, first, mid, last, sorted);
	}
}

归并排序中的递归算法可用下图说明

归并排序中的递归算法可用下图说明

分割那部分的 first，mid，last 是用来区分2-路，即第一路为 [ first, mid )，第二路为 [ mid, last )。上面图解的两路为一小整体，后面的合并就是前面的反分割。

由上面可知，归并排序的时间复杂度对输入序列的排序状态不敏感，可以从其分割合并过程来看，类似于一棵二叉树，其每一层的时间复杂度为O(N)，共有logN层，所以其总的时间复杂度为O(NlogN)，由于归并排序需要额外等大的暂存单元，另外还需要递归深度为 logN 的栈空间，所以其空间复杂度为O(N+logN)（一般认为是O(N)），在适用场合受限。由程序可知，只有元素小于的情况下才会放到前面，所以当两相同元素比较时，不会改变位置，所以归并排序也是一种稳定的排序算法。总的说来，归并排序是一种比较占用内存，但却效率高且稳定的算法。

最后浅谈一下，本排序算法所用到的分治法：

分解：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题；

解决：若干个子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题；

合并：将各子问题的解决合并为原问题的解。

引用到排序算法中就是，先将整体待排序序列分解成若干个子问题，其问题也是解决排序，当分解不充分时，不能直接解决，再次分解，知道可以直接解决该问题。当每个与原问题相同形式的子问题解决之后，意味着原问题也得到了解决，只需要将这若干个子问题合并起来就可以了。