归并排序

#归并排序

• 什么是归并排序
• 分割阶段
• 合并阶段
• 时间复杂度
• 特点

#什么是归并排序

归并排序采用分治法：先把序列对半分割，直到每个子序列只有一个元素（自然有序），然后把有序的子序列两两合并，直到合成一个完整的有序序列。

就像把一副扑克牌分成两半各自排序，然后合并——合并时每次取两边较小的牌。

#分割阶段

以 6 4 3 7 5 1 2 为例，不断对半分割：

          6  4  3  7  5  1  2
         /                    \
    6  4  3              7  5  1  2
    /      \            /          \
  6  4    3          7  5       1  2
  /  \    |          /  \       /  \
 6    4   3         7    5     1    2

每个子序列只剩一个元素，分割结束

#合并阶段

把有序的子序列两两合并——每次比较两个子序列的首位，取较小的放入结果：

合并 6 和 4:     [4, 6]          ← 比较 6 和 4，4 小先取
合并 3:          [3, 4, 6]       ← 3 比 4 小，直接放前面... 
                                  不，实际是 [4,6] 和 [3] 合并 → [3,4,6]

合并 [4,6] 和 [3,7]:
  比较 4 和 3 → 取 3
  比较 4 和 7 → 取 4
  比较 6 和 7 → 取 6
  取 7
  结果: [3, 4, 6, 7]

合并 5 和 1:     [1, 5]
合并 [1,5] 和 [2]: [1, 2, 5]

合并 [3,4,6,7] 和 [1,2,5]:
  3 vs 1 → 取 1
  3 vs 2 → 取 2
  3 vs 5 → 取 3
  4 vs 5 → 取 4
  6 vs 5 → 取 5
  取 6, 7
  结果: [1, 2, 3, 4, 5, 6, 7]

#时间复杂度

归并排序的时间复杂度为 O(n log n)，且最好、最坏、平均都是 O(n log n)。

#特点

• 稳定排序：相等元素的相对顺序不变
• 时间复杂度始终为 O(n log n)，没有最坏情况退化
• 需要额外空间 O(n)（不是原地排序）
• 是一种递归的分治算法
• 适合外部排序（数据量大到内存放不下时，可以用归并排序的思想）

#小结

• 归并排序：先分割到单个元素，再两两合并
• 时间复杂度 O(n log n)，稳定排序
• 需要额外空间，适合需要稳定排序的场景
• 分治法的经典应用，递归实现