How to merge three sorted arrays without using any unnecessary space?

Question

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 ?

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
– Marc van Leeuwen, Commented Jun 28, 2015 at 5: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
– Marc Glisse, Commented Jun 28, 2015 at 7:11

Bhoot · Accepted Answer · 2015-06-28 04:47:51Z

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.

answered Jun 28, 2015 at 4:47

Bhoot

2,6431 gold badge24 silver badges36 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Saraph Over a year ago

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).

Marc Glisse Over a year ago

AFAICT, the OP is not asking for in-place merge, he looks happy to keep res2 and only wants to get rid of res.

Community · Accepted Answer · 2017-05-23 11:43:48Z

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.

edited May 23, 2017 at 11:43

CommunityBot

11 silver badge

answered Jun 28, 2015 at 4:50

Ron Thompson

1,0966 silver badges13 bronze badges

Collectives™ on Stack Overflow

How to merge three sorted arrays without using any unnecessary space?

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related