CareerCup

First traverse through array N and place all gaps to the right -- O(n)
for(int i=0,j=0;i<n;i++)
if(a[i]!=' ')
a[j++]=a[i];

merge arrays from right to left -- O(n+m)

are the gaps in N continuous or in between elements???

In between the elements!

void swap(int[] a, int i, int j) {
    if (a[i] == a[j]) {
        return;
    }
    a[i] ^= a[j];
    a[j] ^= a[i];
    a[i] ^= a[j];
}
void merge(int[] a1, int[] a2, int n1, int n2) {
    // push gaps to right
    for (int j = 0, k = 0; i < n1; ++j) {
        if (a1[j] != -1) { // -1 is gap
            swap(a1, j, k++);
        }
    }
    int i1 = n1 - n2 - 1;
    int i2 = n2 - 1;
    int i = n1 - 1;
    while (i1 >= 0 && i2 >= 0) {
        if (a1[i1] > a2[i2]) {
            a1[i--] = a1[i1--];
        } else {
            a1[i--] = a2[i2--];
        }
    }
    while (i1 >= 0) {
        a1[i--] = a1[i1--];
    }
    while (i2 >= 0) {
        a1[i--] = a2[i2--];
    }
}

Assuming we can destroy array M and gaps are represented by ' '.
below is the code

void merge(char[] a, char[] b){
int j = 0;
for(int i= 0;i<a.length;i++){
  if(j>=b.length)
          break;//Array is Sorted
  if(a[i]==' '){
           if(i==a.length() || a[i+1]>b[j]){
              swap(a[i],b[j])
              j++;            
           }else{
              swap(a[i],a[i+1])
           }
  }else{
      if(b[j]<a[i])
            swap(b[j],a[i]);
  }
}

#include <iostream>
using namespace std;

#define INVALID_NUM -1
#define SA 10
#define SB 03


int a[10] = {1, INVALID_NUM, INVALID_NUM, 4, 5, INVALID_NUM, 7, 8, 9, 10};
int b[3] = {2, 3, 6};
void insert(int a[], int &rb);

void merge_sortedArrays(int a[], int b[]);

int main()
{
int i;
cout<<"\nOriginal Arrays:\nA: ";
for (i=0; i<10; i++)
	cout<<a[i]<<" ";
cout<<"\nB: ";
for (i=0; i<3; i++)
	cout<<b[i]<<" ";
cout<<"\n";
merge_sortedArrays(a, b);
cout<<"Merged Array:\n";
for (i=0; i<10; i++)
	cout<<a[i]<<" ";
cout<<"\n";

return 0;
}

void insert(int a[], int &rb)	{
	int start=0; int end = SA-1;
	int mid = (start+end)/2, i=0;
//	cout<<"rb="<<rb<<" ";
//	cout<<"-----bfor loop:: mid = "<<mid<<" start="<<start<<"   end="<<end<<"\n";
	while(mid <end && mid>start)	{
		if(a[mid] == INVALID_NUM)	{
			//mid++;
			int down_inv=mid, up_inv=mid;
			while (a[down_inv]==INVALID_NUM) down_inv++;
			while (a[up_inv]==INVALID_NUM) up_inv--;
			
			if(a[down_inv]>rb && rb>a[up_inv]) {
				mid = down_inv-1;
				break;
			}
			else if(a[up_inv]>rb)	{
				end=up_inv;
				mid = (start+end)/2;
			}
			else	{
				start = down_inv;
				mid = (start+end)/2;
			}
//			cout<<"-----INVALID_NUM; mid = "<<mid<<" start="<<start<<"   end="<<end<<"\n";
		}
		else	{
			if(a[mid] > rb)
				end = mid;
			else
				start = mid;
			mid = (end+start)/2;
//			cout<<"-----mid = "<<mid<<" start="<<start<<"   end="<<end<<"\n";
		}
	}	// finisj=hed finding the correct place to insert the number;
//	cout<<"--got mid="<<mid<<"    ";
	int void_up=0, void_down = SA;
	for(i=end; i<SA && a[i]!=INVALID_NUM; i++);
	void_down=i;
	for(i=end; i>0 && a[i]!=INVALID_NUM; i--);
	void_up=i;
	#define UP 0
	#define DOWN 1
	int shift_dir = ((mid-void_up)>(void_down-mid))?DOWN:UP;
	switch(shift_dir)	{
		case UP:
//			cout<<"shift UP;\n";
			for(i=void_up;i<mid;i++)
				a[i]=a[i+1];
		break;
		case DOWN:
//			cout<<"shift DN;\n";
			for(i=void_down;i>mid;i--)
				a[i]=a[i-1];
		break;
	}
	a[mid]=rb;
cout<<"---Insertion result :";
for (i=0; i<10; i++)
	cout<<a[i]<<" ";cout<<"\n";
//cout<<"----------------------------------------\n";
}

void merge_sortedArrays(int a[], int b[])	{
int i=0;
for(i=0; i<SB; i++)	{
		int &rb = b[i];
		insert(a, rb);
	}
}

public void merge(int a[],int []b){
while(i<a.length && j<b.length){
if(a[i]=="-1"){
i++;
}
if(b[j] =="-1"){
j++;
}
if(a[i] < b[j]){
i++;
}
else{
swap(a[i],b[j]);
i++;
}
}
}
for(int i=0;i<a.length;i++){
if(a[i] == "-a"){
shiftup(a,i);
}
}
}

aakash01's solution is right and the order is also linear. So I am wondering why complicate the solution.

OK, I'm totally confused. This is too simple, and I'm not sure why everybody writing some complex codes to solve this. We need to just combine the 2 Arrays and if the question is not asking to have the first array sorted after the merge, things are much easier. You can just swap whenever you find the " " in the Array 1.

public static void merge2Arrays(String[] a1, String[] a2){
		for(int i=0,j=0;i<a1.length;i++ ){
			 if(a1[i]==" "){
				 a1[i] = a2[j];
				 j++;
			 }
		}	
	}