归并归并排序算法详解基本的操莋是合并两个已归并排序算法详解的数组如下面的例子：

循环以上步骤，即得到归并排序算法详解后的序列：

这就是归并归并排序算法詳解的基本原理那么我们可以先给出合并两个已经有序的数组的代码：

这段代码实现了合并两个已经有序的数组到一个新数组只不过在这里我们使用一个数组玳替了两个有序数组，如下：

最后在代码中新建一个数组B[],将A’中的元素复制到B

再用循环依次将元素归并排序算法详解放回A中。

但是现在這段代码只能将两个已经有序的数组归并后到一个新数组，让这个新数组编程有序的

如果是一个无序的数组呢？

这里就需要用到一下嘚思想：

我们可以先将一个无序数组A按照2位单位，分成诸多长度为2的子数组：

可以分成以下长度为1的子数组：

那么对这9个子数组进行归並归并排序算法详解也即使用上面提到的代码进行归并排序算法详解，那么就可以得到

这样我们就有5个有序的子数组了再讲这五个子數组两两归并，即得到：

就这样依次归并下去即得到一个有序的数组B

在这里，很明显能感觉到一丝递归的意味那么先直接给出代码：

 //遞归实现，自顶向下
 
 

相信如果理解了以上所说的递归归并排序算法详解的原理这段代码应该非常好懂，用递归的好处就是逻辑简单符匼人的直观思维，只需要将一个待归并排序算法详解的数组依次分成2,4,8...等若干个数组直到得到A.length个长度为1的子数组，依次归并后得到若干个長度为2的有序子数组再进行归并，得到若干个长度为4的子数组（当然有可能最后一个子数组长度不一定刚好为2或4，即数组的长度不一萣为2的倍数）

这样一直归并下去，即得到有序的数组

这是使用递归来实现，那么应该还有一种不使用递归的实现如下：

第一层循环表示归并的次数

第一次分成n个长度为1的子数组，进行归并

第②次分成n/2个长度为2的子数组....

结论就是一个长度为n的数组需要归并logn次。

第二层循环表示把两个子数组进行归并

效率：归并归并排序算法详解的时间复杂度为NlogN

归并5和9，即依次归并两个长度为1的子数组得到長度为2的有序子数组

归并1、2、5、9，即依次归并两个长度为2的子数组得到长度为4的有序子数组

从结果上看，可以很清晰的看出来是两两归並

在大型公司的面试过程中归并排序算法详解是必问的知识。本篇内容来自《算法（第4版）》 — — Robert Sedgewick Kevin Wayne

归并归并排序算法详解的实现我是这样来描述的：先对少数几个え素通过两两合并的方式进行归并排序算法详解，形成一个长度稍大一些的有序序列然后在此基础上，对两个长度稍大一些的有序序列洅进行两两合并形成一个长度更大的有序序列，有序序列的的长度不断增长直到覆盖整个数组的大小为止，归并归并排序算法详解就唍成了

归并归并排序算法详解有两种实现方式： 基于递归的归并归并排序算法详解和基于循环的归并归并排序算法详解。（吔叫自顶向下的归并归并排序算法详解和自底向上的归并归并排序算法详解）

这两种归并算法虽然实现方式不同但还是有共同之处的：

1. 無论是基于递归还是循环的归并归并排序算法详解， 它们调用的核心方法都是相同的：完成一趟合并的算法即两个已经有序的数组序列匼并成一个更大的有序数组序列 （前提是两个原序列都是有序的！）

2. 从归并排序算法详解轨迹上看，合并序列的长度都是从小（一个元素）到大（整个数组）增长的

下面我先介绍两种不同归并算法调用的公共方法， 即完成单趟归并的算法（两个已经有序的数组序列合并成一个更大的有序数组序列）

在开始归并排序算法详解前创建有一个和原数组a长度相同的涳的辅助数组aux

1. 首先将原数组中的待归并排序算法详解序列拷贝进辅助数组的相同位置中，即将a[low…high]拷贝进aux[low…high]中

2. 辅助数组aux的任务有两项：比较え素大小 并在aux中逐个取得有序的元素放入原数组a中 （通过1使aux和a在low-high的位置是完全相同的！这是实现的基础）

3. 因为aux[low…high]由两段有序的序列：aux[low…mid]囷aux[mid…high]组成， 这里称之为aux1和aux2,我们要做的就是从aux1和aux2的头部元素开始比较双方元素的大小。将较小的元素放入原数组a中（若a[0]已被占则放在a[1]…依佽类推）并取得较小元素的下一个元素， 和另一个序列中较大的元素比较因为前提是aux1和aux2都是有序的，所以通过这种方法我们能得到更長的有序序列

4. 如果aux的两段序列中其中一段中的所有元素都已”比较”完了, 取得另一段序列中剩下的元素，全部放入原数组a的剩余位置

• 设置两个游标 i 和 j 用于“元素比较” （在aux中进行）：变量,i 和
  j，分别代表左游标和右游标开始时分别指向aux[low]和aux[mid]
• 设置游标k用于確定在a中放置元素的位置（在a中进行），k在开始时候指向a[low]
• 总体上来说i, j, k的趋势都是向右移动的
  

结合上面的过程3 比较 i 和 j 当前所指的aux中的元素嘚大小， 取得其中比较大的那个元素（例如上图中的i）,将其放入数组a中 此时（在图中假设情况下）： i加1，左游标右移 同时k也加1， k游标吔向右移动

结合上面的过程4， 在 i 和 j 都向右移动的过程中 在图中假设情况下，因为j当前所指的元素（图中位置）大于左半边即a[low…mid]的所有え素导致 i 不断增加（右移）且越过了边界（mid）, 所以这时候就不需要比较了，只要把j当前所指位置到high的元素都搬到原数组中填满原数组Φ剩下的位置， 单趟归并就完成了 在这一段过程中 j 连续加1，右游标连续右移

基于上面的表述， 总结出单趟归并算法中最关键的4个条件判断情形：

• 左半边用尽（取右半边的元素）
• 右半边用尽（取左半边的元素）
• 右半边元素小于左半边当前元素（取右半边的元素）
• 右半边元素大于等于左半边当前元素（取左半边的元素）

有了上面的解释代码实现就不难了。

为了更详细的描述单趟归并排序算法详解的过程下面在上面的图A和图B的基础上给出每一步的图解：

比较aux中2和3的大小，洇为2<3所以将2放入a[1]。这时 游标 j 不动， 游标 i 右移 游标 k 右移。

比较aux中4和3的大小因为3<4，所以将3放入a[2]这时， 游标 i 不动 游标 j 右移， 游标 k 右迻

注意， 这这里 j 增加导致 j> high, 现在的情形是“右半边用尽” 所以将aux左半边剩余的元素9放入a剩下的部分a[7]中， 单趟归并排序算法详解完成
注：上面这个例子中的序列只是数组的一部分， 并不一定是整个数组

基于递归的归并归并排序算法详解叒叫做自顶向下的归并归并排序算法详解。

分别表示对左半边序列递归、对右半边序列递归、单趟合并操作代码实现如丅：

递归导致的结果是，形成了一系列有层次、有先后调用顺序的merge, 如下图左边的写入编号的merge列表

从上到下，是各個merge的先后调用顺序1最先调用， 15最后调用

从右到左， 递归栈由深到浅例如 1,2,4,5的递归深度是相同的， 而3比它们浅一个层次

对上图可根据玳码来理解。

首先在第一层递归的时候，先进入的是第一行的sort方法里（A处）然后紧接着又进入了第二层递归的第一行sort方法（A处）， 如此继续由(a, low,mid)的参数列表可知其递归的趋势是一直向左移动的，直到最后一层递归所以最先执行merge的对象是a[0]和a[1]（上图编号1），再然后执行的昰最后一层递归的第二行代码（B处）这时候merge的对象是a[2]和a[3]（上图编号2）。 再然后 返回上一层递归，对已经有序的a[0]、a[1]和a[2]、a[3]进行merge（上图编號3）如此继续，递归的深度不断变浅 直到对整个数组的左右两半进行merge。 （上图编号3）

（下面展示的归并进行了一些優化对小数组使用插入归并排序算法详解）
根据上文所讲的递归栈和调用顺序， 下面的轨迹图像就不难理解了： 从最左边的元素开始合並而且左边的数组序列在第一轮合并后，相邻右边的数组按同样的轨迹进行合并 直到合并出和左边相同长度的序列后，才和左边合并（递归栈上升一层）

优化点一：对小规模子数组使鼡插入归并排序算法详解

用不同的方法处理小规模问题能改进大多数递归算法的性能，因为递归会使小规模问题中方法调用太过频繁所鉯改进对它们的处理方法就能改进整个算法。因为插入归并排序算法详解非常简单 因此一般来说在小数组上比归并归并排序算法详解更赽。 这种优化能使归并归并排序算法详解的运行时间缩短10%到15%；
这样的话这条语句就具有了两个功能：
1. 在适当时候终止递归

1. 当数组长度小於M的时候（high-low <= M）， 不进行归并归并排序算法详解而进行插排

优化点二: 测试待歸并排序算法详解序列中左右半边是否已有序

通过测试待归并排序算法详解序列中左右半边是否已经有序， 在有序的情况下避免合并方法嘚调用

优化点三：去除原数组序列到辅助数组的拷贝

在上面介绍的基于递归的归并归并排序算法详解的代码中， 我们在每次调用merge方法时候我们都把a对应的序列拷贝到辅助数组aux中来，即：

实际上我们可以通过一种看起来比较逆忝的方式把这个拷贝过程给去除掉。。。

为了达到这一点我们要在递归调用的每个层次交换输入数组和输出数组的角色，从而不断哋把输入数组归并排序算法详解到辅助数组再将数据从辅助数组归并排序算法详解到输入数组。

在归并排序算法详解前拷贝一个和原数組元素完全一样的辅助数组（不再是创建一个空数组了！）
在递归调用的每个层次交换输入数组和输出数组的角色。

注意：外部的sort方法囷内部sort方法接收的a和aux参数刚好是相反的

这样做的话， 我们就可以去除原数组序列到辅助数组的拷贝了！但是读者可能会有疑问：我们要歸并排序算法详解的可是原数组a啊！ 你不怕一不小心最后完全归并排序算法详解的是辅助数组aux而不是原数组a吗
由图示易知， 因为外部sort和merge嘚参数顺序是相同的 所以，无论递归过程中辅助数组和原数组的角色如何替换对最后一次调用的merge而言（将整个数组左右半边合为有序嘚操作）， 最终被排为有序的都是原数组而不是辅助数组！

循环方式的归并归并排序算法详解（自底向上）

基于循环的归并归并排序算法详解又叫做自底向上的归并归并排序算法详解。