时间和空间复杂度

时间复杂度：

• 最佳、平均和最坏情况： O(n log n)
  • 数组大约会被每次平分，递归深度为 log n；每一层合并都需要 O(n) 的工作量。运行时间不受输入顺序影响。

空间复杂度：

• O(n)
  • 与原地排序不同，归并排序会在合并时创建新数组，因此需要与输入规模成正比的额外内存。

总结：

• 归并排序速度快且运行时间稳定：所有情况下都是 O(n log n)。
• 它是稳定的，因此相等的元素会保持原有顺序。
• 代价是合并时需要额外的 O(n) 内存。