归并排序

现在所讨论的算法基于归并这个操作，即将两个有序的数组归并成一个更大的有序数组。人们根据这个操作发明出了一种递归排序算法：归并排序。要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。

原地归并的抽象方法

要想实现归并，一种直截了当的方式是将两个不同的有序数组归并到第三个数组中，这种方法虽然简单，但是不适合处理大数组的排序。我们会进行多次的归并，而每次归并都会产生新的数组，这可能会产生一些问题。所以我们希望的是原地归并，就是可以使归并后仍然存回原数组中，节省空间。我们用方法merge(arr,lo,mid,hi) 。它会将子数组arr[lo…mid] 和arr[mid+1…hi] 归并成一个有序的数组并将这个结果存放在arr[lo…hi] 当中。

void merge(int arr[], int lo, int mid, int hi) {
	int i = lo, j = mid + 1;
	for (int k = lo;k <= hi;k++)
		aux[k] = arr[k];
	for (int k = lo;k <= hi;k++) {
		if		(i > mid)				arr[k] = aux[j++];
		else if (j > hi)				arr[k] = aux[i++];
		else if (less(aux[j], aux[i]))	arr[k] = aux[j++];
		else							arr[k] = aux[i++];
	}
}

可以看到，我们的方法利用了一个外部定义的辅助数组。先将所有数据复制到辅助数组aux[] 中，然后再归并回arr[] 中。第二个for循环是归并的主要操作，进行了4个条件判断：左半边用尽（取右半边元素）、右半边用尽（取左半边元素）、右半边当前元素小于左半边当前元素（取右半边元素）以及右半边当前元素大于左半边当前元素（取左半边元素）。

自顶向下的归并排序

基于原地归并的抽象，我们实现了一种递归归并，体现出了算法设计当中的分治思想。

void MergeSort(int arr[], int lo, int hi) {
	if (hi <= lo)return;
	int mid = lo + (hi - lo) / 2;
	MergeSort(arr, lo, mid);//将左半边排序
	MergeSort(arr, mid + 1, hi);//将右半边排序
	merge(arr, lo, mid, hi);//归并结果
}

如下图所示，要将a[0…15] 排序，sort() 方法会调用自己将a[0…7] 排序，再在其中调用自己将a[0…3] 和a[0…1] 排序。在将a[0] 和 a[1] 分别排序后，我们开始将a[0] 和a[1] 归并。第二次归并是a[2] 和a[3]，然后是a[0…1] 和a[2…3]，以此类推。

自底向上的归并排序

递归的归并排序是算法设计中分治思想的典型应用。我们将一个大问题分割成小问题分别解决，然后用小问题的答案解决整个大问题。另一种归并排序的算法没有使用递归，我们先归并那些微型数组，然后成对归并得到的子数组。首先我们进行两两归并（将两个大小为1的数组归并成一个2个元素的数组），然后进行四四归并（将两个大小为2的数组归并成一个4个元素的数组），然后进行八八归并…以此类推。

void MergeSortBU(int arr[],int n) {
	for (int sz = 1;sz < n;sz = sz + 1)
		for (int lo = 0;lo < n - sz;lo += sz + sz)
			merge(arr, lo, lo + sz - 1, min(lo + sz + sz - 1, n - 1));
}

自底向上的归并排序会多次遍历整个数组，根据子数组的大小进行两两归并。子数组的大小sz的初始值为1，每次加倍。

总结

当数组长度为2的幂时，自顶向下和自底向上的归并排序所用的比较次数和数组访问次数正好相同，只是顺序不同。自底向上的归并排序比较适合用链表组织的数据。归并排序告诉我们，问题的答案往往不止一种。可以化整为零，然后递归地解决问题；也可以循序渐进地解决问题。归并排序的两种不同的方式都可以很好地解决排序问题，各有千秋。