mergesort

归并排序 是最高效的排序算法之一。该排序算法的时间复杂度是 O(log n) ，归并排序是由分割和合并组成的。将一个比较大的问题分割成若干容易解决的小问题，然后进行合并，得到一个最终的结果。归并排序的口诀就是先分割，后合并。 举个例子，假定你手中有如下一摞卡牌： mergeSort1.png mergeSort1.png 排序算法的排序过程大致是这样的： 1，首先，将这一摞牌分成两半，这样就得到了两摞无序的卡牌。 mergeSort2.png mergeSort2.png mergeSort3.png mergeSort3.png 1，最后，以和分割相反的顺序，将每一摞卡牌合并。在每一次合并的过程中，将数据按照规则进行排序。由于每一小摞的卡牌都已经有序，在合并的时候会比较容易些。 mergeSort4.png mergeSort4.png 首先，先将数组分成两半： 将数组分割一次远远不够，需要递归调用分割函数，直到不能在分割为止。这样的话，每一个子部分都只包含一个元素。按照这种思路，我们将 mergeSort 更新至如下所示： 这里有两个变动点： 1，对函数进行了递归调用，在数组中有且只有一个元素时，停止递归调用。 2，对原数组的左右子数组都调用 mergeSort 。 如上代码在能通过编译之前，仍然还有很多事情去做。现在已经完成了数组分割部分，是时候去关注于合并了。 合并左右子数组是该算法的最后一步。为了更算法更明了一些，单独创建一个 merge 方法。 merge 方法的职责仅仅是 将两个将两个有序的数组合并成一个有序的数组。在 mergeSort 函数中，增加以下方法： 最后附上本文的相关代码 DataAndAlgorim 参考链接 《Data Structures & Algorithms in Swift》

归并排序是一种稳定的算法（即在排序过程中大小相同的元素能够保持排序前的顺序，3212升序排序结果是1223，排序前后两个2的顺序不变），这一点在某些场景下至关重要。 归并排序是最常用的外部排序方法（当待排序的记录放在外存上，内存装不下全部数据时，归并排序仍然适用，当然归并排序同样适用于内部排序）。 归并排序中“分”与“合”的过程是结合在一起的，即每一趟都在做“分”与“合”的工作，并不是先“分”完再“合”（“分”很简单，不就是一直二分二分直到不可再分呗，额，这么想就错了，分完就合不起来了，切记“分”与“合”是结合在一起的）

归并排序 （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 递归版 Go 迭代版 递归版

归并排序写法有：递归写法、迭代写法、原地归并写法、自底向上归并写法、多路归并写法。 1、递归写法：这是最基本的归并排序写法，它通过递归将数组不断地分成更小的子数组，然后再将它们合并成一个有序数组。这种写法的优点是简单易懂，但是在处理大数据量时可能会导致栈溢出。 2、迭代写法：与递归写法不同，迭代写法使用循环代替递归，将数组分成若干个小块，然后逐一合并这些小块。这种写法的优点是可以避免栈溢出的问题，但是代码比递归写法稍微复杂一些。 3、原地归并写法：这种写法不需要使用额外的空间，而是直接在原数组中进行排序。它的核心思想是将两个有序的子数组合并成一个有序数组，同时保证不破坏原数组的顺序。 4、自底向上归并写法：这种写法是一种迭代写法的变体，它从底部开始将数组分成小块，然后逐一合并这些小块，直到整个数组被排序。这种写法的优点是可以避免栈溢出的问题，同时也可以利用缓存来提高排序效率。 5、多路归并写法：这种写法将数组分成多个子数组，然后同时对它们进行排序，最后将它们合并成一个有序数组。这种写法可以利用多核处理器的优势，提高排序效率。