归并排序
归并排序（Merge Sort）是分治思想的经典应用。
基本思想
将排序分成三步：分开、排序、合并。
常用的为 2 路归并排序。
合并过程
将两段有序序列合并为一段有序序列。使用三个指针：k 指向目标序列要更新的位置，i 指向第一段序列正在处理的位置，j 指向第二段序列正在处理的位置。
整体排序流程
实际代码中利用栈结构从下向上递归调用：输入整个序列，分治直到只剩一个元素，返回过程中合并。
算法分析
- 时间复杂度：O(n log n)
- 空间复杂度：O(n)
- 稳定性：稳定
归并排序的复杂度很好且是稳定的，但需要额外的 O(n) 空间来存储排序过程中产生的序列。
