归并排序

归并排序基于分治思想：将序列分成若干个子序列，分别排序后再合并为有序序列。

基本思想

1. 将长度为 $n$ 的序列分成两个长度为 $n/2$ 的子序列
2. 对两个子序列分别递归进行归并排序
3. 将两个有序子序列合并成一个有序序列

复杂度

• 时间复杂度：$O(n\log n)$（与初始序列无关）
• 稳定性：稳定
• 空间复杂度：$O(n)$（需要辅助数组）

特点

• 归并排序是外部排序（如对 10TB 数据文件排序）的基础，当内存一次放不下数据时通常采用归并排序法
• 比较次数与序列初始状态无关