归并排序

• 利用归并的思想实现的排序方法 
• 该算法采用经典的分治策略 
• 分治法将问题分(divide)成一些小的问题然后递归求解 
• 治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起

性质

• 时间复杂度：$O(n\log n)$
• 空间复杂度：$O(n)$
• 稳定性：稳定
• 递归深度：为$log2n$
• 比较次数：数量级与序列初始状态无关