如果我在已经排序的数组上应用合并排序，时间复杂度是多少？
通常的合并排序仍然使用O(nlogn)作为排序数据。
但是存在自然的合并排序变体，它为排序数组提供了线性复杂性。
请注意，与 isertion 排序相比，自然合并排序也为任意数据提供了O(nlogn)，后者对于排序数据表现良好，但在最坏的情况下变为二次
根据维基百科的合并排序页面，合并排序具有最佳和最差的情况表现为 O(n log n) 。 给定已排序的数组的输入，合并排序仍需要经历与任何其他数组相同的排序过程。 因此，即使对于排序数组，运行时间仍然会O(n log n) 。
对于已经排序的数组，还有其他算法实际上击败了合并排序，例如插入排序。 对于插入排序，已经排序的数组的性能是O(n)的，即线性的。