算法 · 合并排序

合并排序是一种稳定高效的递归排序，它是利用分而治之法的解决思路惊醒递归排序，合并排序非常稳定，时间复杂度始终都是 O(n log n)，它是一种自上而下的排序方式。

分而治之法：

Divide and conquer，缩写D&C；它的对事情的解决思路是将事情不断地缩小至最小，再将他们逐个击破，最后把问题合并起来解决。它的工作原理是：

1.找出简单的基线条件；2.确定如何缩小问题的规模，使其符合基线条件。

合并排序法：

该排序法充分运用到了分而治之的思考方式；在一组数组中，我们可以将数组的中间数作为基线条件，判断他们大于小于该基线条件，并且放到相应的大小数组中，进行下一次的递归。直到数组不能再次拆解。

图片来自《图解算法》

根据栈的数据结构，栈是一种后进先出（Last In First Out，FIFO）的数据结构，所以当栈达到最低端的时候，会优先返回上图中的[7,8]数组，再一层一层往上返回；因此也可以说合并排序是一种由下而上的排序法。再回到最开始所说的D&C思路，正好是最小化问题->解决->合并最小化问题的解决方案。而且这样做可以减少栈的调用，且合并排序非常稳定，最坏的情况下是O(n log n)，相比起快速排序的最坏情况，因为快速排序极其依赖开发者对基线条件的选择，快速排序的最坏情况是O(n的平方)。

至于代码，没有代码！大家可以根据上述思路实际动手，可以加深理解。在实现递归条件时不要忘记临界点，以免无限堆栈照成死循环。