一、动图演示

二、思路分析

归并排序就是递归得将原始数组递归对半分隔，直到不能再分（只剩下一个元素）后，开始从最小的数组向上归并排序

1.  向上归并排序的时候，需要一个暂存数组用来排序，

2.  将待合并的两个数组，从第一位开始比较，小的放到暂存数组，指针向后移，

3.  直到一个数组空，这时，不用判断哪个数组空了，直接将两个数组剩下的元素追加到暂存数组里，

4.  再将暂存数组排序后的元素放到原数组里，两个数组合成一个，这一趟结束。

根据思路分析，每一趟的执行流程如下图所示：

三、负杂度分析

1.  时间复杂度：递归算法的时间复杂度公式：T[n] = aT[n/b] + f(n) 

无论原始数组是否是有序的，都要递归分隔并向上归并排序，所以时间复杂度始终是O（nlog2n）

2.  空间复杂度：

　　每次两个数组进行归并排序的时候，都会利用一个长度为n的数组作为辅助数组用于保存合并序列，所以空间复杂度为O（n）

 四、Java 代码如下