如何使用合并排序算法就地排序? [英] How to sort in-place using the merge sort algorithm?
问题描述
我知道这个问题不太具体.
I know the question is not too specific.
我想要的只是有人告诉我如何将普通合并排序转换为就地合并排序(或具有恒定额外空间开销的合并排序).
All I want is someone to tell me how to convert a normal merge sort into an in-place merge sort (or a merge sort with constant extra space overhead).
我能找到的(在网上)只有页面说它太复杂了"或超出了本文的范围".
All I can find (on the net) is pages saying "it is too complex" or "out of scope of this text".
就地合并(没有任何额外空间)的唯一已知方法太复杂，无法简化为实际程序.(取自此处)
The only known ways to merge in-place (without any extra space) are too complex to be reduced to practical program. (taken from here)
即使太复杂，如何就地进行归并排序的基本概念是什么?
推荐答案
Knuth 将此留作练习(第 3 卷，5.2.5).确实存在就地合并排序.它们必须谨慎实施.
Knuth left this as an exercise (Vol 3, 5.2.5). There do exist in-place merge sorts. They must be implemented carefully.
首先，简单的就地合并，例如此处 不是正确的解决方案.它将性能降低到 O(N2).
First, naive in-place merge such as described here isn't the right solution. It downgrades the performance to O(N2).
这个想法是对数组的一部分进行排序，同时将其余部分用作合并的工作区.
The idea is to sort part of the array while using the rest as working area for merging.
例如像下面的合并函数.
For example like the following merge function.
void wmerge(Key* xs, int i, int m, int j, int n, int w) {
while (i < m && j < n)
swap(xs, w++, xs[i] < xs[j] ? i++ : j++);
while (i < m)
swap(xs, w++, i++);
while (j < n)
swap(xs, w++, j++);
}
它需要数组xs，两个排序的子数组表示为范围[i, m) 和[j, n)> 分别.工作区从 w 开始.与大多数教科书中给出的标准合并算法相比，该算法在排序后的子数组和工作区之间交换内容.结果，前一个工作区包含合并的排序元素，而前一个工作区中存储的元素被移动到两个子数组中.
It takes the array xs, the two sorted sub-arrays are represented as ranges [i, m) and [j, n) respectively. The working area starts from w. Compare with the standard merge algorithm given in most textbooks, this one exchanges the contents between the sorted sub-array and the working area. As the result, the previous working area contains the merged sorted elements, while the previous elements stored in the working area are moved to the two sub-arrays.
但是，必须满足两个约束条件:
However, there are two constraints that must be satisfied:
- 工作区应该在数组的边界内.换句话说，它应该足够大以容纳交换的元素而不会导致任何越界错误.
- 工作区可以与两个已排序数组中的任何一个重叠；但是，它必须确保没有任何未合并的元素被覆盖.
定义了这个合并算法，很容易想象一个解决方案，它可以对数组的一半进行排序；接下来的问题是，如何处理工作区中剩余的未排序部分，如下图所示:
With this merging algorithm defined, it's easy to imagine a solution, which can sort half of the array; The next question is, how to deal with the rest of the unsorted part stored in work area as shown below:
... unsorted 1/2 array ... | ... sorted 1/2 array ...
一个直观的想法是对另一半工作区进行递归排序，因此只有 1/4 元素尚未排序.
One intuitive idea is to recursive sort another half of the working area, thus there are only 1/4 elements haven't been sorted yet.
... unsorted 1/4 array ... | sorted 1/4 array B | sorted 1/2 array A ...
这个阶段的关键是我们必须合并排序好的1/4元素B与排序的 1/2 元素 A 迟早.
The key point at this stage is that we must merge the sorted 1/4 elements B with the sorted 1/2 elements A sooner or later.
剩下的工作区，只放了1/4的元素，够大可以合并吗甲和乙?不幸的是，它不是.
Is the working area left, which only holds 1/4 elements, big enough to merge A and B? Unfortunately, it isn't.
然而，上面提到的第二个约束给了我们一个提示，如果我们能确保未合并元素不会被覆盖的合并顺序，我们可以通过安排工作区与任一子数组重叠来利用它.
However, the second constraint mentioned above gives us a hint, that we can exploit it by arranging the working area to overlap with either sub-array if we can ensure the merging sequence that the unmerged elements won't be overwritten.
实际上，我们可以对前半部分进行排序，而不是对工作区的后半部分进行排序，并将工作区放在两个已排序的数组之间，如下所示:
Actually, instead of sorting the second half of the working area, we can sort the first half, and put the working area between the two sorted arrays like this:
... sorted 1/4 array B | unsorted work area | ... sorted 1/2 array A ...
这个设置有效地安排了工作区与子阵列A的重叠.这个想法[Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola.``实用的就地归并排序''.北欧计算杂志，1996].
This setup effectively arranges the work area overlap with the sub-array A. This idea is proposed in [Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. ``Practical in-place mergesort''. Nordic Journal of Computing, 1996].
所以剩下的就是重复上面的步骤，将工作区域从1/2、1/4、1/8、……当工作区域变得足够小(比如只剩下两个元素)，我们可以切换到一个平凡的插入排序来结束这个算法.
So the only thing left is to repeat the above step, which reduces the working area from 1/2, 1/4, 1/8, … When the working area becomes small enough (for example, only two elements left), we can switch to a trivial insertion sort to end this algorithm.
这里是基于本文的 ANSI C 实现.
Here is the implementation in ANSI C based on this paper.
void imsort(Key* xs, int l, int u);
void swap(Key* xs, int i, int j) {
Key tmp = xs[i]; xs[i] = xs[j]; xs[j] = tmp;
}
/*
* sort xs[l, u), and put result to working area w.
* constraint, len(w) == u - l
*/
void wsort(Key* xs, int l, int u, int w) {
int m;
if (u - l > 1) {
m = l + (u - l) / 2;
imsort(xs, l, m);
imsort(xs, m, u);
wmerge(xs, l, m, m, u, w);
}
else
while (l < u)
swap(xs, l++, w++);
}
void imsort(Key* xs, int l, int u) {
int m, n, w;
if (u - l > 1) {
m = l + (u - l) / 2;
w = l + u - m;
wsort(xs, l, m, w); /* the last half contains sorted elements */
while (w - l > 2) {
n = w;
w = l + (n - l + 1) / 2;
wsort(xs, w, n, l); /* the first half of the previous working area contains sorted elements */
wmerge(xs, l, l + n - w, n, u, w);
}
for (n = w; n > l; --n) /*switch to insertion sort*/
for (m = n; m < u && xs[m] < xs[m-1]; ++m)
swap(xs, m, m - 1);
}
}
wmerge 之前定义的地方.
Where wmerge is defined previously.
The full source code can be found here and the detailed explanation can be found here
顺便说一下，这个版本不是最快的归并排序，因为它需要更多的交换操作.根据我的测试，它比标准版本更快，标准版本在每次递归中分配额外的空间.但是比优化版要慢，优化版提前将原数组翻倍，再用它做进一步合并.
By the way, this version isn't the fastest merge sort because it needs more swap operations. According to my test, it's faster than the standard version, which allocates extra spaces in every recursion. But it's slower than the optimized version, which doubles the original array in advance and uses it for further merging.
这篇关于如何使用合并排序算法就地排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
