puzzle using arrays

Question

My first array M + N size and second array of size N.

let us say m=4,n=5
a[ ]= 1,3,5,7,0,0,0,0,0

b[ ]= 2,4,6,8,10

Now , how can i merge these two arrays without using external sorting algorithms and any other temporary array(inplace merge) but complexity should be o(n).Resultant array must be in sorted order.

Answer 1

for (i = 0; i < N; i++) {
    a[m+i] = b[i];
}

This will do an in-place merge (concatenation).

If you're asking for an ordered merge, that's not possible in O(N). If it were to be possible, you could use it to sort in O(N). And of course O(N log N) is the best known general-case sorting algorithm...

I've got to ask, though, looking at your last few questions: are you just asking us for homework help? You do know that it's OK to say "this is homework", and nobody will laugh at you, right? We'll even still do our best to help you learn.

Answer 2

Do you want a sorted array ? If not this should do

for(int i=a.length-1,j=0;i >=0; i--) { a[i] = b[j++]; }

Answer 3

Provided a is exactly the right size and arrays are already sorted (as seems to be the case), the following pseudo-code should help:

#    0 1 2 3 4 5 6 7 8
a = [1,3,5,7,0,0,0,0,0]
b = [2,4,6,8,10]
afrom = 3
bfrom = 4

ato = 8
while bfrom >= 0:
    if afrom == -1:
        a[ato] = b[bfrom]
        ato = ato - 1
        bfrom = bfrom - 1
    else:
        if b[bfrom] > a[afrom]:
            a[ato] = b[bfrom]
            ato = ato - 1
            bfrom = bfrom - 1
        else:
            a[ato] = a[afrom]
            ato = ato - 1
            afrom = afrom - 1
print a

It's basically a merge of the two lists into one, starting at the ends. Once bfrom hits -1, there are no more elements in b so the remainder in a were less than the lowest in b. Therefore the rest of a can remain unchanged.

If a runs out first, then it's a matter of transferring the rest of b since all the a elements have been transferred above ato already.

This is O(n) as requested and would result in something like:

[1, 2, 3, 4, 5, 6, 7, 8, 10]

---

Understanding that pseudo-code and translating it to your specific language is a job for you, now that you've declared it homework :-)

Answer 4

You can take a look at in-place counting sort that works provided you know the input range. Effectively O(n).