前面介绍了冒泡、插入、选择排序，下面我们介绍一个个人认为稍微复杂点的排序，归并排序，首先看下归并排序的思路。首先我们先思考一个问题，对于两个有序的数组left与right，我们怎么给他们排序？是不是很简单？一个for循环对left[i]和right[j]进行比较，如果left[i]< right[j],将left[i]插入到新的数组中然后i++；反之将right[j]插入到数组中，然后j++。最后将left或者right数组中剩余的数列拼接到数组后面，就组成了一个有序的新数组。
代码如下：
说到这里大家都理解吧？如果不理解自己在会从头考虑下，我认为这是理解归并排序的第一步，看明白了之后我们在往下看。
那么对于一个无序的数列，怎么将其变成两个有序的数列，这就是归并的核心，一旦变成了两个有序的数列，然后用上面的merge函数，就可以完成这个数列的排序了。
试想首先将一个无序的数列两个无序的数列，大家习惯的思路是采用折半，前一半在前面，后一半在后面，将这两个无序数列分别排序，就可以构成两个有序的数列，但是细想下，对于每一半的无序数列又采取什么排序算法那？冒泡？插入还是选择？他的时间复杂度都是O(n^2),这样一来不仅仅没有降低算法的时间复杂度，同时增加了代码的复杂度。再顺着这个思路思考下，将上面两个无序的数列继续折半下去，最终变成两个单元数数列，这样就可以将其看成两个有序的数列，然后用上面的merge函数进行合并，这样就形成了一个有序的数列，然后再将后面的两个单元数数列进行重复的操作，这样就形成了多个2个元素的有序数列，依次类推，多个4个元素的有序数列，最终形成多个元素的有序数列。说到这里不知道大家理解了吗？盗个图放在这里看看：
对应代码如下：
至此，归并排序完成。
