c++ - 如何在不使用任何不必要空间的情况下合并三个排序数组？

Question

例如，我编写了 C++ 代码来合并三个数组，但在这里您可以看到，我必须首先合并前两个数组，然后将其结果数组合并到第三个数组。

while (p < n1 && q < n2)    // n1,n2,n3 are sizes of a,b,c respectively 
{
    if (a[p] < b[q])    
    {
        res[r] = a[p];  // res is array is intermediate merged array
        r++;
        p++;
    }
    else
    {
        res[r] = b[q];
        r++;
        q++;
    }
}

while (q < n2)
{
    res[r] = b[q];
    r++;
    q++;
}

while (p < n1)
{
    res[r] = a[p];
    r++;
    p++;
}

while (s < r && t < n3)
{
    if (res[s] < c[t])
    {
        res2[r2] = res[s];  // res2 is finally merged array
        r2++;
        s++;
    }
    else
    {
        res2[r2] = c[t];
        r2++;
        t++;
    }
}

while (s < r)
{
    res2[r2] = res[s];
    s++;
    r2++;
}

while (t < n3)
{
    res2[r2] = c[t];
    r2++;
    t++;
}

我不想在我的程序中使用中间数组。有什么办法可以做到吗？

此外，是否有任何方法可以一次性合并任意数量的已排序数组？

Answer 1

我认为您正在研究就地合并排序，特别是最佳稳定合并。这不是一个微不足道的问题，已经在文献中进行了详细讨论。你可以开始阅读这个 here .

引自论文摘要:

This paper shows how to stably merge two sequences A and B of sizes m and n, m ≤ n, respectively, with O(m+n) assignments, O(mlog(n/m+1)) comparisons and using only a constant amount of additional space. This result matches all known lower bounds and closes an open problem posed by Dudzinski and Dydek in 1981. Our algorithm is based on the unstable algorithm of Mannila and Ukkonen. All techniques we use have appeared in the literature in more complicated forms but were never combined together. They are powerful enough to make stable all the existing linear in-place unstable algorithms we are aware of. We also present a stable algorithm that requires a linear number of comparisons and assignments which we consider to be the simplest algorithm for in-place merging.