合并排序基础

Merge Sort 是一种分而治之的算法。它将长度为 n 的输入列表连续分成两半，直到有 n 个大小为 1 的列表。然后，将列表对与每个步骤中添加的列表对中较小的第一个元素合并在一起。通过连续合并并通过比较第一元素，构建排序列表。

一个例子：

时间复杂性 ：T(n) = 2T(n/2) + Θ(n)

可以使用递归树方法或主方法来解决上述重现。如果主法的情况 II，则复发的解决方案是Θ(nLogn)。时间的复杂性归并排序在所有 3 个例（Θ(nLogn) 最差，平均和最佳 ）作为合并排序总是划分阵列中的两半，并采取线性时间合并两半。

辅助空间 ：O(n)

算法范式 ：分而治之

就地排序 ：不在典型的实施中

稳定 ：是的