arrays - 排序数组（时间复杂度）

Question

如果我有一个数组，其中单元格 0-N 已排序，单元格 N+1 直到 M+N，未排序。对数组进行排序的最佳时间复杂度是多少？

谢谢！

---

编辑：

谢谢 ！！如果我想就地这样做，它会改变复杂性吗？

Answer 1

首先，只对 M 个未排序的元素进行排序。这需要时间 O(M log M) 使用基于比较的排序（如快速排序、合并排序或堆排序）。

然后将两个排序的段（长度为 N 和 M）合并在一起。这需要时间 O(M + N)。

所以最好的时间复杂度，使用基于比较的排序，是 O(M + N + M log M)。