归并排序
++++++++++++++++
:strong:`归并排序`\ 是一种递归的高速排序算法。时间复杂度为 :math:`O(n\log n)`\ ，达到了理论上的时间复杂度下限。但它并不是速度最快的排序算法，快速排序、堆排序在平均情况下的实际运行速度都比归并排序要略快一些。然而归并排序在实际应用中用途特别广泛，原因有三：
1. 归并排序的表现极其稳定，不受原序列有序程度的影响，对它来说没有什么最好情况、最差情况或者平均情况，不管什么情况一律是 :math:`O(n\log n)` 的时间效率。
2. 归并排序适用于外部排序，例如存放在海量存储设备中的超大型数据库排序，基本上就是用的归并排序算法的外排序版本，而快速排序和堆排序都不太适合改造成外排序版本。
3. 归并排序的编程非常简单，只要会归并过程就可以轻松写出一个正确的归并排序来（参考：:ref:`归并过程的说明<24A1-merge-ref>`\ ）。
归并排序是一种稳定的排序算法，它的缺点是有较大的内存空间使用，但是在算法竞赛问题中一般空间不太成为大问题。所以归并排序无论在算法竞赛问题中，还是在实践应用中都是非常重要的一种排序算法。
**归并排序的原理和实现**
归并排序的算法思路起源于对两个有序序列的归并。假设要排序的序列可以分为前后两个部分，这两个部分各自都是有序的，例如整数序列 [1,3,4,5,1,2,6,7]，它的前4个数的子序列 [1,3,4,5] 和后4个数的子序列 [1,2,6,7] 各自都是有序子序列。那么对这个序列的排序就变得非常简单，只要用一次归并过程把前后两个有序子序列归并起来就可以了，这个过程是 :math:`O(n)` 时间的。
当然，在实际编程中，要原地归并前后两个子序列不是不可以，但是会比较复杂。所以实际编程一般都会新开辟一块空间用作临时数组，把两个子序列归并到这个临时数组里面去，归并完成后再把这个临时数组里已经有序的新序列复制回原数组。这个过程利用C++语言的动态内存管理功能和块复制功能可以轻松的实现。
例如要归并数组 ``int d[]`` 中的两个连续有序子序列，用三个位置变量 ``l, r, mid`` 分别表示左、右、中三个下标，标识出两个子序列的左闭右开区间，分别为 ``d[l:mid]`` 和 ``d[mid:r]``\ 。
我们可以先编写一个工具函数来实现这个归并过程。这里要用到动态内存管理和内存块复制，下面是归并函数的代码：
.. literalinclude:: ../../codes/253_merge_sort.cpp
:language: c++
:lines: 2-3, 10-12, 51-76
如果一个序列的前后两半都是有序的，那么一次归并就能完成排序了。但是怎样让序列的前后两半都变成有序的呢？我们可以把原序列一分为二，然后先对前后半进行排序。怎样对前后两半进行排序？最简单的办法就是递归地使用归并排序。这就是归并排序的基本思路。
于是整个归并排序会这样递归下去，在对前一半进行排序的时候，仍然会将其分为前后两半，分别进行同样的归并排序。对后一半的排序也一样，对第二次细分出来的四个子序列也一样。这个递归过程最终会遇到一种可以直接返回结果的特殊情况，即要排序的子序列中只有一个元素。单个元素天生有序，不需要再进一步递归下去了，所以我们不去处理它，直接返回就可以了。这就是二分归并排序的终止条件。现在我们就可以写出归并排序的算法结构了，对序列 :math:`A` 中的一段范围 :math:`A[l,r]` 进行排序：
.. admonition:: 归并排序算法
:math:`\text{MergeSort}(A, l, r):`
:math:`mid\leftarrow\lfloor(l+r)/2\rfloor`
:math:`\text{IF }mid-l\gt1\text{ THEN MergeSort}(A, l, mid)`
:math:`\text{IF }r-mid\gt1\text{ THEN MergeSort}(A, mid, r)`
:math:`\text{Merge}(A, l, r, mid)`
其中的子算法 :math:`\text{Merge}(A, l, r, mid)` 前面已经完成了代码编写，即归并过程的工具函数，所以编写这个程序就非常简单了吧。在编写代码之前，为了加深对递归过程的直观理解，我们先来看一个简单的实例，假设我们要对序列 [3, 2, 9, 1] 进行排序。
原序列长度为4，故分为 [3, 2] 和 [9, 1] 两个子序列并先后递归进行排序再进行归并
1. 归并排序 [3, 2]，其长度为2，故分为 [3] 和 [2] 两个子序列并先后递归进行排序再进行归并
1. 归并排序 [3]，其长度为1，不做任何处理即结束
2. 归并排序 [2]，其长度为1，不做任何处理即结束
3. 归并 [3] 和 [2]，得到子序列 [2, 3]
2. 归并排序 [9, 1]，其长度为2，故分为 [9] 和 [1] 两个子序列并先后递归进行排序再进行归并
1. 归并排序 [9]，其长度为1，不做任何处理即结束
2. 归并排序 [1]，其长度为1，不做任何处理即结束
3. 归并 [9] 和 [1]，得到子序列 [1, 9]
3. 归并 [2, 3] 和 [1, 9]，得到 [1, 2, 3, 9]
至此排序完成。
对于长度不是2\ :superscript:`k`\ 的序列，其排序过程也是一样的，无非有时候不同分支的结束时点会不同。例如对序列 [3, 2, 9, 1, 4] 进行排序：
原序列长度为5，按照除2取整得到的二分点为2，即分为 [3, 2] 和 [9, 1, 4] 两个子序列，先后递归排序再进行归并
1. 归并排序 [3, 2]，其长度为2，故分为 [3] 和 [2] 两个子序列并先后递归进行排序再进行归并
1. 归并排序 [3]，其长度为1，不做任何处理即结束
2. 归并排序 [2]，其长度为1，不做任何处理即结束
3. 归并 [3] 和 [2]，得到子序列 [2, 3]
2. 归并排序 [9, 1, 4]，其长度为3，故被分为 [9] 和 [1, 4] 两个子序列并先后递归进行排序再进行归并
1. 归并排序 [9]，其长度为1，不做任何处理即结束
2. 归并排序 [1, 4]，其长度为2，分为 [1] 和 [4] 两个子序列先后进行递归排序再进行归并
1. 归并排序 [1]，其长度为1，不做任何处理即结束
2. 归并排序 [4]，其长度为1，不做任何处理即结束
3. 归并 [1] 和 [4]，得到子序列 [1, 4]
3. 归并 [9] 和 [1, 4]，得到子序列 [1, 4, 9]
3. 归并 [2, 3] 和 [1, 4, 9]，得到 [1, 2, 3, 4, 9]
排序结束。
下面是归并排序的代码：
.. literalinclude:: ../../codes/253_merge_sort.cpp
:language: c++
在许多算法书中归并排序的主函数会用另一种写法：
.. code-block:: c++
void merge_sort(int d[], int l, int r)
{
if (r - l == 1) return;
int mid = (l + r) / 2;
merge_sort(d, l, mid);
merge_sort(d, mid, r);
merge(d, l, r, mid);
}
这两种写法本质上是一样的，你能看明白吗？
**归并排序算法分析**
归并排序在每一次归并的时候，会用到和被归并部分长度相等的临时空间。但是每次归并结束后这些空间会被释放，所以临时空间的占用不积累，最大的时候等于原序列所占的空间，即最后一次归并的时候。所以归并排序的空间复杂度为 :math:`O(n)`\ 。
从归并排序的过程可以看出，它对原序列中元素的有序程度完全没有感觉。无论原序列中的元素是不是有序、逆序，也不管其有序程度多大，算法总是不管不顾地进行不断二分不断归并，一次不会多一次不会少。因此归并排序的时间复杂度任何情况下都是一样的，无所谓最好、最差还是平均情况。
归并排序是一个非常典型的简单递归算法，其工作量可以用一个递推公式来表示。从算法的主过程可以看出，工作分为三部分，两次二分的递归调用和一次归并，递归的工作量各为原工作量的一半，归并的工作量为最多 :math:`n` 次元素比较。所以整个排序过程的工作量：
.. math::
T(n)=2T({n\over2})+n,T(1)=0
可以用迭代法，也可以用递归树的方法来求解这个递推方程。这里不需要考虑数据量 :math:`n` 的取值情况，假设它是 :math:`n=2^k` 就好。对于不是2的幂次方的情况，我们在计算时间复杂度时就取恰好比它大的那个2的幂次方作为上界，比如对于 :math:`n=6`\ ，就取 :math:`n=8` 作为上界，这并不会对结果的阶造成影响。
对所有基于二分的算法进行时间复杂度分析时，都可以这样只考虑 :math:`n=2^k` 的情况。用迭代法计算如下：
.. math::
\begin{align}
T(n)&=T(2^k)=2T({n\over2})+n=2T(2^{k-1})+n\\
&=2[2T(2^{k-2})+{n\over2}]+n=2^2T(2^{k-2})+2n\\
&=2^2[2T(2^{k-3})+{n\over4}]+2n=2^3T(2^{k-3})+3n\\
&=\cdots\\
&=2^kT(1)+kn=kn\\
\therefore T(n)&=O(n\log n)
\end{align}
作为练习，请用画递归树的方法解出这个递推方程。
最后要说明的是，归并排序是稳定的排序算法。为什么？还是请自行思考。
**归并排序算法的优化**
归并排序的理论时间复杂度已经达到了最低限 :math:`O(n\log n)`\ ，在实际应用中，它会略微地比快速排序慢一些。那么在实践中能不能对它再进行一些改进呢？
前面我们说过，二分插入排序在数据量比较小的时候，实际运行速度会比利用递归的 :math:`O(n\log n)` 算法还略快一些，原因是它没有递归调用带来的额外开销。那么我们能不能对归并排序做这样的优化，当待排序的子序列中元素少于一定的数量时，就不要再进一步递归下去了，直接用二分插入算法完成这个子序列的排序就可以了。这样是不是能够让归并排序变得更加快一些呢？这个问题留作一次实验练习，请按照下面的要求完成实验。
实验目的：测试二分插入排序和归并排序的实际运行速度比较，并按照比较结果对二分归并排序进行优化尝试，评估优化效果。
实验步骤：
1、编写标准的归并排序和二分插入排序程序，输入格式为第一行一个整数 :math:`n`\ ，:math:`0\lt n \lt 10^5`\ ，第二行为 :math:`n` 个 ``int`` 型范围内的整数，数和数之间用一个空格隔开。程序的输出均为一行，即已经排好序的 :math:`n` 个输入整数，数和数之间以一个空格隔开。完成上述两个程序的编写并进行正确性测试。
2、在上述两个程序中，增加对排序部分的运行时间测定。此处需要注意三个问题：
1. 当数据量大时，输入和输出会占用许多时间，而且根据计算机环境的不同，可能会有很大的波动，测定排序时间不应包括输入和输出使用的时间。
2. 整数排序算法的运行时间非常快，当数据量不大时，用毫秒会精度不够，无法比较，请设法使用微秒（百万分之一秒）为单位进行测速。
3. 同样数据量的多次排序，运行时间也会有上下波动，为了测试精确，请设法尽量消除误差。
3、下载此工具软件：:download:`随机整数序列生成器<../../codes/tools/randints.cpp>`\ ，自行编译成可执行程序。使用此工具，输入一个整数n，就会按照上述的排序程序输入格式生成一批随机的整数，可以用作排序程序的输入。有两种使用方法：
1. 使用输出重定向功能将生成的数据保存在一个输入文件中，例如 ``./randints > s1.in`` 即可将生成的数据保存到文件 ``s1.in`` 中，然后使用输入重定向功能，例如 ``./merge_sort < s1.in`` 将这个输入文件作为排序程序的输入。
2. 使用管道功能，即连续运行两个程序，并将第一个程序的输出直接输送给第二个程序用作输入，例如执行命令 ``./randints | ./merge_sort`` 会先运行 ``randints`` 程序，然后运行 ``merge_sort`` 程序，并将前者的输出直接作为后者的输入。
上述的输入输出重定向和管道功能无论是Linux系统的Terminal终端窗口还是Windows系统的cmd命令窗口都是支持的，唯一的不同是Windows系统下运行当前目录里的程序时不需要在程序名称之前加上表示当前目录的 ``./``\ ，直接用程序名就可以了，Linux下则必须有 ``./``\ ，包括管道命令的后一个程序也必须有。
对输入输出重定向和管道命令还有疑惑的可以参考这个网页：\ `Linux命令中的管道和重定向 <https://blog.csdn.net/u014532901/article/details/79742175>`_
4、从少到多地使用多种数据量对两种排序算法的运行速度进行测试，查看二分插入排序在数据量小的时候会不会快于归并排序，如果会则尝试找到分界点。注意，计算机程序运行的环境错综复杂，分界点不会是一个确定不变的数值，不同的计算机上分界点也会略有不同，但总应该会有一个比较靠谱的分界区域，大概在几百左右。
5、尝试利用找到的分界点对归并排序进行优化，编写程序，测试正确，并用上述方法测定运行速度，和标准的归并排序程序进行对比，得出实验结论。