归并排序

归并排序

采用了分治的思想

• 归并在 $O(n)$ 内完成
  • 二路归并
  • 优化：只进行一次 new 和 delete
• $T(n)=2T(n/2)+O(n)$，由Master Theorem，时间复杂度为 $O(n\log n)$
• 同层内的子任务独立，易于并行化
• 稳定性：归并时对于相等元素优先将前缀归并进主数组，即可实现稳定性。
• 最坏情况下最优，为 $O(n\log n)$，但最优情况下也需 $O(n\log n)$
• 序列足够短时，递归带来的开销会相对更大，可以改用冒泡排序 降低空间复杂度？ 若用列表实现，可以实现就地

自然归并排序

归并排序在最优情况下仍需 $O(n\log n)$ 时间，能否优化？

• 顺串：连续的有序子数列
• 用迭代代替递归，每轮依次扫描，每找到两个顺串进行一次合并，合并与标准归并排序相同，每轮扫描用时为 $O(n)$。每次合并两个顺串，因此每轮扫描顺串总数至少减半，因此至多进行 $O(\log n)$ 次。显然，总渐近时间复杂度为 $O(n\log n)$
• 此时，如果数组部分有序，可以极大减少排序时间，最优情况下（数列有序），复杂度为 $O(n)$
• 空间复杂度仍为 $O(n)$