高效合并两个数组 - 一个有序，另一个无序

Question

我正在处理一个问题，它包含一个有 n 个元素的已排序数组，后面跟着一个长度为：

1. O(logn)
2. O(sqrt(n))

的未排序数组。如何高效地对整个列表进行排序？在上述两种情况下应该使用哪种排序方法？

- Neel

---

在第一种情况下，我们可以使用O(logn)的信息吗？我们能否使用任何数据结构并更有效地对其进行排序？ - Neel

Answer 1

由于将单个元素插入数组并保持其排序的时间复杂度为O(n)，因此您无法获得比这更好的结果。

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

• 对较小的数组进行排序：O(logn*loglog(n)) 或 O(sqrt(n)*log(sqrt(n))) 分别是两种情况。
• merge(part1,part2)：O(n+logn) 或 O(n+sqrt(n))，无论如何都是O(n)¹。

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

---

（1）它是真实的，因为对于每个k>0,m>0，log(n)^k渐进地小于n^m，特别是对于k=1，m=1/2。
证明基于两边取对数：

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

最后一个显然是真的（对于大的n和常数k, m > 0），因此这个论点是正确的。 从这里我们可以得出结论，sqrt(n)*log(n) < sqrt(n) * n^1/2 = n，因此它确实是O(n)。

- amit

---

你的逻辑是正确的，只是O(sqrt(N)*log(N)) < O(N)这一点不太明显。 - salva

@salva：我来澄清一下，基本上对于每个k，m，log(n)^k在渐进意义下都比n^m小，特别地，当k=1，m=1/2时。 - amit

@salva：我在这个声明中添加了详细的解释作为脚注。 - amit

Answer 2

你可以简单地对未排序的数组进行排序，然后对这两个已排序的数组执行合并（就像归并排序算法一样）。

- Jean Logeart

Answer 3

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

- SkyWalker

Answer 4

假设part1和part2的大小分别为O(log n)和O(sqrt(n))。因此，如果您从part2中选择一个元素，并通过使用二分搜索在part1中找到该位置，然后递归执行此操作，直到part2的元素为空，总运行时间将变为O(sqrt(n) log(log n))。

- Saroj Jena

---

通过二分查找在part1中找到part2元素的位置将需要logn的时间。但是将该元素放置在part1中正确的位置将需要线性时间（O(n)）。这里part1中的排序数组有n个元素。有两个问题。第一个问题中未排序数组的长度为logn，第二个问题中未排序数组的长度为sqrt(n)。 - Neel