归并排序

归并排序的基本思想是：利用递归和分而治之（Divide and Conquer）的方法将待排序的数组划分成越来越小的局部数组，再对局部数组排序，最后利用递归的方法将已经排序完毕的局部数组整合成越来越大的有序数组。归并排序包括两个步骤：
一、分割(Divide)；
二、整合(Conquer)：
首先来看一下归并排序中用到的下标：left 指局部数组开头的元素，right 指局部数组末尾+1 的元素，mid 是 left 和 right 相加除以2，对结果向下取整。

归并排序中用到的下标.png
接下来我们通过对数组 {9, 6, 7, 2, 5, 1, 8, 4, 2} 对归并排序进行说明：
归并排序.jpg
一、分割
向下的蓝色箭头代表分割，箭头边的数字表示处理顺序，分割由mergeSort负责,当局部数组只剩下一个元素时，mergeSort不做任何处理直接结束，如果不是，则计算数组的中央位置 mid, 将 left 到 mid (不包含mid)视作前半部分，mid 到 right (不包含right)视作后半部分，再分别套用mergeSort；具体步骤如下所示：
Step 1: left=0, right=9, 因此 mid=4, 调用mergeSort进行分割，将0~4（即9、6、7、2）视作前半部分，；
Step 2: left=0, right=4, 因此 mid=2, 调用mergeSort进行分割，将0~2（即9、6）视作前半部分；
Step 3: left=0, right=2, 因此 mid=1, 调用mergeSort进行分割，将0~1（即9）视作前半部分，此时局部数组只剩一个元素，mergeSort不做任何处理直接结束；
Step 4: left=1, right=2, 将1~2（即6）视作后半部分，此时局部数组只剩一个元素，mergeSort不做任何处理这节结束；
Step 5: 接下来对对 {6} 和 {9} 这这两个局部数组进行合并，因此就有了第二个步骤。
二、整合
向上的橘色箭头代表整合，箭头边的数字表示处理顺序，整合由merge负责。为了方便叙述，在这里将包含 n1 个元素的前半部分已排序数组称为 L，包含 n2 个元素的后半部分有序数组称为 R, 现在我们需要将 L 和 R 中的元素按照升序排列复制到数组 A 中，在这里我们可以利用已排序的性质进行合并，同样我们举个例子进行说明。
合并两个已排序的数组.jpg
Step 5: 调用merge对前半部分数组和后半部分数组进行合并，结果为6、9；
Step 6: left=0, right=4, 因此 mid=2, 调用mergeSort进行分割，将2~4（即7、2）视作后部分；
step 7: left=2, right=4, 因此 mid=3 调用mergeSort进行分割，将2~3（即7）视作前半部分，此时局部数组只剩一个元素，mergeSort不做任何处理这节结束；
Step 8: left=3, right=4, 将3~4（即2）视作后半部分，此时局部数组只剩一个元素，mergeSort不做任何处理这节结束；
Step 9: 接下来调用merge对 {7} 和 {2} 这两个局部数组进行合并，结果为 {2、7}；
Step 10: 调用merge对 {6, 9} {2, 7}这两个局部数组进行合并，结果为 {2, 6, 7, 9}；
Step ........: 以此类推。
Step 24: 最终得到排序的结果为 {1, 2, 2, 4, 5, 6, 7, 8, 9}。
接下来贴上代码：
<pre>
void merge(int A[], int n, int left, int mid, int right){
int n1 = mid - left;
int n2 = right - mid;
for (int i = 0; i < n1; i++) L[i] = A[left+i];
for (int i = 0; i < n2; i++) R[i] = A[mid + i];
L[n1] = R[n2] = SENTINEL;
int i = 0, j = 0;
for (int k = left; k < right; k++){
cnt++;
if (L[i] <= R[j]){
A[k] = L[i++];
}
else{
A[k] = R[j++];
}
}
}
//归并排序
void mergeSort(int A[], int n, int left, int right){
if (left + 1 < right){
int mid = (left + right) / 2;
mergeSort(A, n, left, mid);
mergeSort(A, n, mid, right);
merge(A, n, left, mid, right);
trace(A, n);
}
}
</pre>
运行结果：
运行结果.png
稳定性：归并排序包含不相邻元素间的比较，但并不会直接交换，在合并两个已排序数组的时候，如果遇到了相同元素，只要保证前半部分数组优先于后半部分数组，相同元素的顺序就不会颠倒，因此归并排序属于稳定的排序算法。
复杂度：在merge处理中，合并算法的复杂度为O(n1+n2)，对于本例的输入{9, 6, 7, 2, 5, 1, 8, 4}包含9个元素，若想将其分割成仅包含一个元素的局部数组，需要经历9-5-3-2-1的4次分割，总共分为5层，如果是8个元素，则分为4层。一般来说n个数据大致分为log2(n)层。由于每层执行merge的复杂度为O(n)， 因此归并排序的整体复杂度为O(nlogn)。
总结：归并排序算法虽然高效稳定，但是在处理过程中，除了用于保存输入数据的数组之外，还需要临时占用一部分内存空间。