如何使用O(n)时间复杂度和O(1)空间复杂度，在原地合并两个已排序的整数数组？

Question

例如，给定一个整数数组以及它的两个连续序列的起始位置'b1'和'b2'，还提供了位置'last'，表示第二个序列的结束位置。从array[b1]到array[b2-1]和从array[b2]到array[last]分别按顺序排列，如何用O(n)时间和O(1)空间的代价在原地合并它们？

- pwd

---

这似乎是一道穿着面试服的家庭作业。 - zombat

来吧，没有人会在面试中问这个问题！ - Dr. belisarius

Answer 1

Kronrod的合并排序算法是第一个能够达到O(n)时间复杂度的算法。该算法大致步骤如下：

将数组的两个部分分别分成大小为k=sqrt(n)的块，以它们的第一个元素作为比较基准进行排序。这可以使用选择排序在sqrt(n)^2=O(n)的时间内完成。选择排序的关键特性在于每个块的移动次数都是常数次，因此只有#比较数目是平方级别的。

在这一阶段之后，对于数组中的每个元素A[i]，其下方最多有k-1个“错误排序”的元素，即位置在j<i且A[j]>A[i]的元素。这些元素可能来自另一个已经合并的部分中离它最近的块。请注意，由于块是按它们的第一个元素进行排序的，所以块的第一个元素和所有其他位于其下方的块相对于A[i]已经正确排序。这就是第二阶段可行的原因，即实现了完全排序的数组：

现在将第一个块与第二个块合并，然后将第二个块与第三个块合并，以此类推，使用最后两个块作为临时空间来存储合并的输出。这将破坏最后两个块的内容，但在最后一阶段，它们（连同前一个块）可以使用选择排序在sqrt(n)^2=O(n)时间内进行排序。

- Rafał Dowgird

---

这是一个相当不错的方法，并且在一个段落中解释得很清楚。谢谢Rafal！ - Yo Hsiao

@RafałDowgird 数组如果不能被sqrt(n)整除，确实会使算法变得更加复杂。 - 2501

@2501 非常正确。Kronrod算法并不是一个实用的算法。我认为任何原地合并都不是。免责声明：我可能错过了最新的研究。 - Rafał Dowgird

Kronrod算法在数组中没有足够的唯一元素时会失败，因为块的排序不稳定（这是算法正确执行所必需的）。 - dhruvbird

这个算法在TAOCP的第三卷中被解释，是在5.2.4节的一个练习的解决方案中。 - Gil Vegliach

Answer 2

这绝不是一个简单的问题。虽然使用N-scratch空间进行标准合并比较复杂，但这是可能的，但在实践中很少这样做。自80年代末以来，黄和Langston的论文一直存在，尽管实际实现直到后来才真正出现。早期，L·特拉布-普拉多（Trabb-Prado）于1977年发表的论文比黄和Langston显著地早，但我很难找到该论文的确切文本; 只有参考资料存在。

Geert，Katajainenb和Pasanen于1995年发表的优秀论文渐近高效的原地合并涵盖了多种算法，并引用了Trabb-Prado对该主题的贡献。

- David

---

我在考虑在面试中也这么回答!! :D - letsc

链接（希望）再次恢复正常。 - WhozCraig

@WhozCraig，又挂了。 - gen

稳定排序和合并的最优时间和空间边界（Stable Sorting and Merging with Optimal Time and Space Bounds）Trabb Pardo, Luis I.（该名字经常拼写不同）。 - greybeard

@David，1977年的论文是由L. Trabb Pardo撰写的（不是Trabb-Prado）。 - kristianp

Answer 3

存在真正的原地合并算法，但它们不直截了当，以至于在面试中没有人会独立发明它们-多年来已有论文描述了一系列相当复杂的算法。其中一个是Huang和Langston的《实用就地合并》，CACM 1988年3月。其起始想法是将长度为n的数据分成大小为sqrt(n)的块，并使用一个块，填充着数据中最大的元素，提供缓冲空间用于合并其他块。该论文的介绍如下所述：

"给定两个长度之和为n的有序列表，显然需要O(n)步骤的合并方法还需要线性数量的额外内存。另一方面，可以通过堆排序只使用恒定量的附加空间进行原地合并，但代价是O(n log n)时间"

因此，我声称真正的原地合并可以实现，但并不明显。

- mcdowella

Answer 4

虽然完全不可能在O(n)时间内完成，但我有一个提议可以比O(n^2)更快地完成。 我只使用了代码中的临时空间O(1)。 我相信它应该比O(n^2)运行得更好。

private static int[] mergeSortedArrays(int[] a1, int[] a2) {
        int i = 0, j = 0;
        while (a1[i] != Integer.MIN_VALUE) {
            if (a1[i] > a2[j]) {
                int temp = a1[i];
                a1[i] = a2[j];
                a2[j] = temp;

                for (int k = 1; k < a2.length; k++) {
                    if (a2[k - 1] > a2[k]) {
                        temp = a2[k - 1];
                        a2[k - 1] = a2[k];
                        a2[k] = temp;
                    }
                }
            }
            i++;
        }
        while(j < a2.length){
            a1[i++] = a2[j++];
        }
        return a1;
    }

- Hari

---

我假设没有任何一个数组会有Integer.MIN_VALUE，因为我的代码在这种情况下会失败。我已经在整数后面的a1数组中添加了Integer.MIN_VALUE，这样一旦a1完成处理，我们就可以灵活地将a2元素添加到a1本身中，并最终返回合并后的a1数组和a2元素。 - Hari

Answer 5

这里是O(n-1)内存（n+1）

/**
 * Created by deian on 2016-12-22.
 * We just need track the two smallest numbers 
 */
public class Merge {
    public static void swap(int[] a, int i1, int i2) {
        int t = a[i1];
        a[i1] = a[i2];
        a[i2] = t;
    }

    public static void merge(int[] a) {
        // i1 and i2 - always point to the smallest known numbers
        // it would works as well with two m and n sized arrays 
        int i1 = 0;
        int i2 = a.length / 2;

        System.out.printf("    %s,      i(%d,%d)       \n", Arrays.toString(a), i1, i2);
        for (int di = 0; di < a.length - 1; di++) {
            int ni;
            int oi1 = i1; int oi2 = i2;
            if (a[i1] > a[i2]) {
                ni = i2; i2++;
                if (i2 >= a.length) { i2--; }
            } else {
                ni = i1; i1++;
                if (i1 >= i2) { i1 = di; }
            }
            if (di == i1) { i1 = ni; }
            swap(a, di, ni);
            System.out.printf("#%d: %s, i(%d,%d)s(%d>%d)i(%d,%d) \n", di + 1, Arrays.toString(a), oi1, oi2, ni, di, i1, i2);
        }
        System.out.printf("    %s\n", Arrays.toString(a));
    }

    public static void main(String[] args) {
//        int[] a = new int[]{1, 3, 6, 8, -5, -2, 3, 8};
//        int[] a = new int[]{1, 3, 6, 8, -5, 2, 3, 8};
//        int[] a = new int[]{1, 5, 6, 8, -5, 2, 3, 4};
//        int[] a = new int[]{1, 5, 6, 8, -5, -2, -1, 4};
//        int[] a = new int[]{ 1, 2, 3, 4, 5, 6, 7, 8};
//        int[] a = new int[]{5, 6, 7, 8, 1, 2, 3, 4};
        int[] a = new int[]{1, 3, 5, 7, 2, 4, 6, 8};
        merge(a);
    }
}

- Deian

Answer 6

我几个小时前参加了一次面试（与一家非常重要的公司），并被问到这个问题。 以下是Java的答案

public static void main(String[] args) {
    int A[] = { 1, 3, 5, 6, 9 };
    int B[] = new int[12];
    B[0] = 3;
    B[1] = 6;
    B[2] = 8;
    B[3] = 10;
    B[4] = 11;
    B[5] = 13;
    B[6] = 15;
    mergeInB(A, B, 7);
    for (int n : B)
        System.out.print(n + " ");
}



 /**
 * @param a
 * @param b - it will be modified
 * @param j = length of b
 */
public static void mergeInB(int[] a, int[] b, int j) {
    int i = a.length - 1, k;
    j --;
    for (k = b.length-1; k >= 0; k--) {
         if (i >= 0 && j >= 0) {
             if (a[i] > b[j]) {
                 b[k] = a[i];
                 i --;
             }
             else 
              {
                 b[k] = b[j];
                 j --;
             }               
         }
         else break;
    }

    while(i>=0 && k >=0) {
         b[k] = a[i];
         k --;
         i --;
    }

    while(j>= 0 && k >=0) {
         b[k] = b[j];
         j--;
         k--;
     }
}

- merlincita_pj