实现常用排序算法（二）归并排序

简介

归并排序排序(Merge Sort)与快速排序不同，它是一种稳定排序（Stable Sort），也就是说，对于数组中相等的元素，归并排序可以保证它们排序后相对位置不改变。由于我们用整数int的数组的排序作例子，这个特点并不能很好地表现出来，实际上在某些场景中这个性质很重要，因此c++特别地在std::sort之外提供了一个稳定排序算法std::stable_sort。

归并排序也是分治算法，归并排序重复进行合并操作，不断地将两个排序好的数组合并成一个排序好的数组，最终完成整个数组的排序。归并排序有两种实现，一种是空间复杂度$O(1)$的原地（In-place）算法，另一种需要额外$O(n)$的空间。

不使用额外空间的归并排序需要用到一个叫做手摇算法（Block Swap Algorithm/内存反转算法/三重反转算法）的技巧来交换数组中的两块内存，这会引入大量的变量交换操作从而增加算法消耗的时间，甚至有可能使归并排序退化到$O(n^2)$，本质上是一种时间换空间的方法，这里不多做介绍。较为常用的还是非原地的常规写法，这里也用这种实现方法来演示。

非原地版本的归并排序的平均、最坏时间复杂度都是$O(n \log n)$，非常优秀，但是实践中往往比快速排序慢上不少。

实现

void mergeSort(int *begin, int *end){
    if(end - begin < 2) return; 
    int *mid = begin + (end - begin) / 2;
    mergeSort(begin, mid); 
    mergeSort(mid, end); //先将数组划分为两份，每份进行排序后再合并。
    int *tmp = new int[end - begin]; //申请额外的空间来临时存放合并后的结果
    int *i = begin, *j = mid, *k = tmp;
    while(i < mid && j < end) //只要两个部分都还有元素就一直比较，取较小的元素放进tmp中。
        if(*j < *i) *(k++) = *(j++); //这样的写法相当于 {*k = *j; ++k; ++j;}
        else *(k++) = *(i++);
    while(i < mid) *(k++) = *(i++); //退出上面的while循环后，两部分应该一个为空，一个非空
    while(j < end) *(k++) = *(j++); //将非空的那个全部放到tmp中
    memcpy(begin, tmp, (end - begin) * sizeof(int)); //将tmp中的元素拷贝回原位。
    delete tmp; //删除申请的空间，防止内存泄露
    return;
}