algorithm - 使用插入排序对部分排序的数组进行排序

Question

我有一个数组，第一个直到 N 元素被排序，N+1 直到元素 N+M 未排序（数组由 N+M 元素组成）。使用插入排序对该数组进行排序的复杂性是多少？我认为是 (N+M)^2，是这样吗？

Answer 1

如果要使用插入排序，则需要 O(M*(M+N)) 操作。但是，更好的方法是在 O(M*lgM) 中对未排序的部分进行排序，然后在 O(N+M) 中合并两个已排序的部分。