如何使用合并排序算法进行就地排序？

Question

如何使用合并排序算法进行就地排序？

我知道这个问题不太具体。

我想要的只是有人告诉我如何将一个普通的合并排序转换为就地合并排序(或者一个具有固定额外空间开销的合并排序)。

我所能找到的(在网上)只是写着“太复杂了”或者“超出了这篇文章的范围”的页面。

唯一已知的合并方式(没有任何额外的空间)过于复杂，无法简化为实用程序。(已采取)从这里开始)

即使太复杂，如何使合并排序就位的基本概念是什么？

Answer 1

关键步骤是获取合并它本身就在原地。这并不像那些消息来源所说的那么困难，但是当你尝试的时候，你会失去一些东西。查看合并的一个步骤：[.名单-分门别类...|x.名单-A...|y.名单-B...]我们知道分门别类序列比其他的都少，x比其他的东西都少A，而那个y比其他的东西都少B..在下列情况下x小于或等于y，您只需将指针移动到A一张。在下列情况下y小于x，你得洗牌y过了整个.A到分门别类..最后一步是造成这一代价的原因(除了在退化的情况下)。它通常更便宜(特别是当数组实际上只包含每个元素的单个单词时，例如指向字符串或结构的指针)，以换取时间，并有一个单独的临时数组，您可以在它们之间来回排序。