algorithm - 在不使用额外数组的情况下实现归并排序？

Question

我最近阅读了很多关于合并排序的文章，我想知道是否有一种方法可以在不使用至少一个额外数组的情况下进行合并排序。可能吗？

Answer 1

显然是这样。 This paper描述就地归并排序:

Two in-place variants of the classical mergesort algorithm are analysed in detail. The first, straightforward variant performs at most N log 2 N + O(N ) comparisons and 3N log 2 N + O(N ) moves to sort N elements. The second, more advanced variant requires at most N log 2 N + O(N ) comparisons and "N log 2 N moves, for any fixed " ? 0 and any N ? N ("). In theory, the second one is superior to advanced versions of heapsort. In practice, due to the overhead in the index manipulation, our fastest in-place mergesort behaves still about 50 per cent slower than the bottom-up heapsort. However, our implementations are practical compared to mergesort algorithms based on in-place merging.

Jyrki Katajainen、Tomi Pasanen、Jukka Teuhola，“实用就地合并排序”(1996 年)。