c# - 无需外部存储就地合并

Question

我想将两个具有排序值的数组合并为一个。由于两个源数组都存储为大型数组的后续部分，我想知道您是否知道将它们合并到大型存储中的方法。意思是就地合并。

我发现的所有方法都需要一些外部存储。他们通常需要 sqrt(n) 临时数组。没有它有有效的方法吗？

我正在使用 C#。也欢迎其他语言。提前致谢!

Answer 1

据我所知，如果不显着增加必要的比较次数和元素移动次数，合并两个(甚至排序的)数组将无法就地工作。请参阅:merge sort .但是，存在阻塞的变体，它们能够通过使用长度为 sqrt(n) 的临时数组对长度为 n 的列表进行排序 - 正如您所写的那样 - 通过仍然保持相当低的操作数。它还不错 - 但它也不是“无”，显然是你能得到的最好的。

对于实际情况，如果你负担得起，你最好使用一个临时数组来合并你的列表。