0

For example I've written C++ code to merge three arrays, but here you can see that first I had to merge first two arrays and then merge its resulting array to third array..

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++;
}

I don't want to use intermediate array in my program.Is there any way I can do it?

Also, Is there any methodology using which we can merge any number of sorted arrays in one go ?

Shreevardhan
  • 12,233
  • 3
  • 36
  • 50
SHUBHAM
  • 1
  • 2
  • Why are you posing the question for three (sorted) arrays? The fundamental problem would seem to in-place merge **two** sorted arrays. This is hard, but once you can do that, you can easily do the case of three or higher, either by generalising the method, or if that is not possible by repeatedly merging two at a time. – Marc van Leeuwen Jun 28 '15 at 05:12
  • The algorithm for 3 arrays is the same as for 2. Among the 3 first elements, chose the smallest, push it to the result, and advance the pointer in the array where this smallest came from (be careful about the tests for when an array becomes empty). For any number of arrays, use a heap to keep track of the order of the first elements. – Marc Glisse Jun 28 '15 at 07:11

2 Answers2

1

I think you are looking at in place merge sort, specifically optimal stable merging. This is not a trivial problem, and has been discussed in literature at length. You can start reading about this here.

Quoted from the abstract of the paper:

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.

Bhoot
  • 2,614
  • 1
  • 19
  • 36
  • These three arrays are sorted. Merge sort for that would be `O((m+n+o)*log(m+n+o))`, but it can be done in `O(m+n+o)`. – Saraph Jun 28 '15 at 04:50
  • AFAICT, the OP is not asking for in-place merge, he looks happy to keep res2 and only wants to get rid of res. – Marc Glisse Jun 28 '15 at 07:16
0

Sorry to burst your bubble, but this isn't practicable with two arrays, let alone N arrays.

Reference: how to merge two sorted integer array in place using O(n) time and O(1) space cost

Note: I said impracticable, not impossible. But unless you're writing a PhD thesis, you're going to have to deal with at least O(n) extra space required.

Community
  • 1
  • 1
Ron Thompson
  • 1,086
  • 6
  • 12