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

Question

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

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

我(在网上)所能找到的所有页面都是说“它太复杂”或“超出本文范围”的页面。

The only known ways to merge in-place (without any extra space) are too complex to be reduced to practical program. (taken from here)

即使它太复杂了，如何就地进行归并排序的基本概念是什么？

Answer 1

Knuth 将其留作练习(第 3 卷，5.2.5)。确实存在就地合并排序。它们必须谨慎实现。

首先，像 here 中描述的那样简单的就地合并不是正确的解决方案。它将性能降级为 O(N²)。

想法是对数组的一部分进行排序，同时将其余部分用作合并的工作区域。

例如像下面的合并函数。

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开始。与大多数教科书给出的标准合并算法相比，该算法在排序后的子数组和工作区之间交换内容。结果，前一个工作区包含合并后的排序元素，而工作区中存储的前一个元素被移动到两个子数组。

但是，必须满足两个约束条件:

1. 工作区应该在数组的范围内。换句话说，它应该足够大以容纳交换的元素而不会导致任何越界错误。
2. 工作区可以与两个排序数组中的任何一个重叠；但是，它必须确保没有任何未合并的元素被覆盖。

定义了这个合并算法，很容易想象一个解决方案，可以对数组的一半进行排序；接下来的问题是，如何处理存储在工作区中的剩余未排序部分，如下所示:

... unsorted 1/2 array ... | ... sorted 1/2 array ...

一个直观的想法是对另一半工作区进行递归排序，这样只有1/4的元素还没有排序。

... unsorted 1/4 array ... | sorted 1/4 array B | sorted 1/2 array A ...

这个阶段的重点是我们必须合并排序后的1/4元素B与排序的 1/2 元素 A 迟早。

剩下的是工作区，只容纳1/4的元素，大到可以合并甲乙？不幸的是，事实并非如此。

然而，上面提到的第二个约束给了我们一个提示，如果我们能保证合并顺序不会覆盖未合并的元素，我们可以通过安排工作区域与任一子数组重叠来利用它。

实际上，我们可以不对工作区的后半部分进行排序，而是对前半部分进行排序，并将工作区放在两个排序数组之间，如下所示:

... sorted 1/4 array B | unsorted work area | ... sorted 1/2 array A ...

此设置有效地安排了工作区与子阵列 A 的重叠。这个想法在 [Jyrki Katajainen、Tomi Pasanen、Jukka Teuhola 中提出。 ``实用的就地归并排序''。北欧计算杂志，1996 年]。

所以只剩下重复上面的步骤，工作区从1/2，1/4，1/8，…减少，当工作区变得足够小时(比如只剩下两个元素) ，我们可以切换到平凡插入排序来结束这个算法。

下面是基于这篇论文在 ANSI C 中的实现。

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。

可以找到完整的源代码here详细解释可见here

顺便说一句，这个版本不是最快的归并排序，因为它需要更多的交换操作。根据我的测试，它比标准版本更快，标准版本在每次递归时分配额外的空间。但它比优化版本慢，优化版本提前将原始数组加倍并用于进一步合并。