介绍
归并排序 (MERGE-SORT) 是利用归并的思想实现的排序方法, 该算法采用经典的分治 (divide-and-conquer) 策略 (分治法将问题分(divide) 成一些小的问题然后递归求解, 而治 (conquer) 的阶段则将分的阶段得到的各答案 "修补" 在一起, 即分而治之).
image.PNG
以看到这种结构很像一棵完全二叉树, 本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现). 分阶段可以理解为就是递归拆分子序列的过程.
时间复杂度
时间复杂度: O(nlogn).
来源: http://www.jianshu.com/p/3e6816485843