arrays - 有效地合并两个数组 - 一个已排序，另一个未排序

Question

我正在解决一个问题，该问题有一个由 n 个元素组成的排序数组，后跟一个未排序的长度数组

1. O（登录）
2. O(sqrt(n))

如何最有效地对整个列表进行排序？在上述两种情况下我应该使用哪种排序？

Answer 1

由于将单个元素插入数组并保持排序是O(n)，因此您无法做得更好。

因此，对于这两种情况 - 对较小的数组进行排序然后使用merge(part1,part2)will be O(n)，因此在渐近复杂度方面是最优的。

• 排序较小的数组：O(logn*loglog(n))，或O(sqrt(n)*log(sqrt(n))分别的情况。
• merge(part1,part2):O(n+logn)或O(n+sqrt(n)),无论如何都是O(n)^{1 。}

因此，两种情况的总复杂度都是O(n)，这对于这个问题是最优的。

---

(1) 这是真的，因为对于每个，特别是对于，log(n)^k都渐近地小。 证明是基于双方的日志：n^mk>0,m>0k=1, m=1/2

log (log(n)^k) <? log(n^m) <=>
k*log(log(n)) <? m*log(n)

最后一个显然是正确的（对于 largen和 constant k,m>0），因此该声明是正确的。
由此我们可以得出结论，sqrt(n)*log(n) < sqrt(n) * n^1/2 = n确实如此O(n)。

Answer 2

您可以简单地对未排序的数组进行排序，然后对这两个排序的数组进行合并（如在合并排序算法中）。

Answer 3

很简单，对第二部分进行排序并将其与第一部分合并（与合并排序相同）。两个已排序子数组的合并步骤为 O(n)。

Answer 4

分别假设part1和part2大小 r O(log n) 和 O(sqrt(n))。因此，如果您使用二分查找从 log(log n) 中选择一个元素part2并在其中找到位置part1，并递归执行直到元素part2不为空，则总运行时间变为 O(sqrt(n) log(log n)）。