归并排序

归并排序 （Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为。1945 年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

这里面提到了两个概念，分别是 分治（法） 和递归，它们是什么呢？

分治法（Divide and Conquer）是基于多路分支递归求和的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解就是子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法中的快速排序和归并排序，傅立叶变换中的快速傅立叶变换…

分治模式在每层递归时都有三个步骤：

递归（英语：Recursion），又译为递回，在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况，如函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

归并排序算法完全遵循分治模式，直观上，其操作步骤如下：

当待排序的序列长度为 1 时，递归“开始回升”，在这种情况下无须作任何工作，因为长度为 1 的每个序列都已排好序。

MERGE 的详细工作过程如下：

我们必须证明第 12～17 行 for 循环的第一次迭代之前该循环不变式成立，且在该循环的每次迭代时保持该不变式，当循环终止时，该不变式须提供一种有用的性质来证明算法的正确性。

前面我们分析了分治算法的过程，我们可以把 MERGE 作为归并排序算法中的一个子程序来用。

上面已经对分治法做了正确性证明，归并排序的正确性不言而喻。

分治算法运行时间的递归式来自基本模式的三个步骤，即分解、解决和合并。假设 T(n) 是规模为 n 的一个问题的运行时间。若问题规模足够小，如对某个常量 c，n≤c，则直接求解需要常量时间，可以将其写成 O(1)。假设把原问题分解成 a 个子问题，每个子问题的规模是原问题的 1/b。为了求解一个规模为 n/b 的子问题，需要 T(n/b) 的时间，所以需要 aT(n/b) 的时间来求解 a 个子问题。如果分解问题成子问题需要时间 D(n)，合并子问题的解成原问题的解需要时间 C(n)，那么得到递归式：

现在我们来讨论归并排序。假定问题规模是 2 的幂（不是 2 的幂时也能正确地工作），归并排序一个元素的时间是常量，当有 n>1 个元素时，分解运行的时间如下：

为了分析归并排序，我们可以将 D(n) 与 C(n) 相加，即把一个函数与另一个函数相加，得到的和是一个 n 的线性函数，即。把它与来自“解决”步骤的项 2T(n/2) 相加，将给出归并排序的最坏情况的运行时间

将递归式重写，得到

其中，常量 c 代表求解规模为 1 的问题所需要的时间以及在分解步骤与合并步骤处理每个数组元素所需要的时间。(相同的常量一般不可能刚好即代表求解规模为 1 的问题的时间又代表分解步骤与合并步骤处理每个数组元素的时间。通过假设 c 为这两个时间的较大者并认为我们的递归式将给出运行时间的一个上界，或者通过假设 c 为这两个时间的较小者并认为我们的递归式将给出运行时间的下界，我们可以暂时回避这个问题。两个界的阶都是，合在一起将给出运行时间为 )。

求解递归式的过程如下图所示：

可以看出，树根 cn 通过递归分解，直到规模降为 1 后，每个子问题只要代价 c。分解步骤一***经历了次，即树高为层，每层的代价为 cn，因此总代价为。

上面我们已经知道了，总代价为，忽略低阶项和常量 c，归并排序的时间复杂度为 O(nlogn)。

归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间，但是这个申请额外的内存空间，会在合并完成之后释放，因此，在任意时刻，只会有一个临时的内存空间在使用，临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

Javascript 递归版

迭代版

递归版