CareerCup

Idea is simple start filling from end of array B. Take two pointers one pointing A's last element and other pointing B's last element(not including extra space left in B).
Now compare them and put which is bigger at the end of B. Now forward the pointer which ever the number was larger.Compare again and Keep doing. Finally both array will get merged.
No extra space needed and complexity will be O(B.length).

Full working code here :
awesomecoder.blogspot.com/2012/08/merge-2-sorted-arrays-without-using.html

void mergeArray(int *A,int *B,int m,int n){
	//A has m elements, B has n-m elements
	int i=m-1,j=n-m-1,k=n-1;
	while(i>=0 && j>=0){
		if(A[i] > B[j]){
			B[k--] = A[i--];
		} else {
			B[k--] = B[j--];
		}
	}
	if(j<0){
		while(i>=0){
			B[k--] = A[i--];
		}
	}
}

public class Problem_1_Merge_B_into_A {

public static void sort_into(int[] a,int[] b,int lastA,int lastB){
int valid_a_end_index=lastA-1;
int valid_b_end_index=lastB-1;
int valid_all_end_index=lastA+lastB-1;
while((valid_a_end_index>=0)&&(valid_b_end_index>=0)){
if(a[valid_a_end_index]>b[valid_b_end_index]){
a[valid_all_end_index]=a[valid_a_end_index];
valid_all_end_index--;
valid_a_end_index--;
}
else{
a[valid_all_end_index]=b[valid_b_end_index];
valid_all_end_index--;
valid_b_end_index--;
}
}
while(valid_b_end_index>=0){
a[valid_all_end_index]=b[valid_b_end_index];
valid_all_end_index--;
valid_b_end_index--;
}

}


public static void main(String[] args) {
int[] a=new int[]{1,3,5,7,9,11,13,14,0,0,0,0,0,0,0,0,0};// valid 8 element
int[] b=new int[]{2,4,5,6,8,10,13,15};//valid 8 element

sort_into(a,b,8,b.length);

for(int i=0;i!=8+b.length;i++)
System.out.print(a[i]+" ");

}

}

good solution

The general idea would be do a single pass on sparse array to push all the data to the end of the array; and then simply merge the array together by walk down the two array and merge them. The code would be similar to what Chengyun has written, except I would put them to the back since I believe the code would be much simpler.

void merge(int [] a, int [] b)
{
    int start = pushback(b);
    int i = 0, idx = 0;
    while (i < a.length && start < b.length)
    {
        if (a[i] > b[start])
        {
            b[idx] = b[start];
            b[start] = -1;
            start ++;
        }
        else
        {
            b[idx] = a[i];
            i++;
        }
        idx++;
    }
}
void pushback(int [] b)
{
    int idx = b.length - 1;
    for (int i = b.length - 1; i >= 0; i--)
    {
        if (b[i] > 0)
        {
            tmp = b[i];
            b[i] = -1;
            b[idx] = tmp;
            idx--;
        }
    }
}

We basically have to use Merge Sort with these two arrays.

void merge(const vector<int>& A, vector<int>& B, int b_filled_to) {
  if (A.size() != B.size() - b_filled_to - 1) return;
  int a_ix = 0;
  int b_ix = 0;
  while (a_ix < A.size()) {
    if (A[a_ix] < B[b_ix]) {
      for (int i = b_filled_to; i >= b_ix; i--) {
        B[i+1] = B[i];
      }
      B[b_ix] = A[a_ix];
      b_filled_to++;
      a_ix++;
    }   
    b_ix++;
  }  
}

public class sorted {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

int a[] = {8,6,10};
int b[] = new int[8];
b[0] = 5;
b[1] = 11;
b[2] = 12;
b[3] = 2;
b[4] = 3;
int temp;


int alen = a.length;
int blen = b.length;
int startpos = blen-alen;

for(int j=startpos,k=0;j<blen;j++,k++)
b[j] = a[k];



for(int i=0;i<b.length;i++)
{
for(int j=0;j<b.length;j++)
{
if(b[i] < b[j])
{
temp = b[i];
b[i] = b[j];
b[j] = temp;
}
}
}

for(int l=0;l<b.length;l++)
System.out.println(b[l]);


}


}

time/space = O(n+m)/O(1)

int * merge(int *a, int *b, int m, int n)
{
	int *p,*q,*r;

	p=a+m;
	q=b+m;
	r=b+m+n;

	while(p!=a||q!=b)
	{
		if(*p>*q)
		{
			*r=*p;
			p--;
		}
		else
		{
			*r=*q;
			q--;
		}
		r--;
	}

	while(p!=a)
	{
		*r=*p;
		r--;
		p--;
	}

	return b;
}

package arrays;

public class BackwardsMergeArray {

	public static void main(String [] args){
		int a[] = {1,4,6,9,12,0,0,0};
		int b[] = {3,7,8};
		
		merge(a,b);
		for (int i : a) {
			System.out.print(i+", ");
		}
	}

	private static void merge(int[] a, int[] b) {
				
		int j = b.length-1;
		int i = a.length-1 -(j+1);
		int count = a.length -1;
		
		while(i>=0 && j>=0){
			if(a[i] > b[j]){
				a[count--] =  a[i];
				i--;
			} else if(a[i]<=b[j]){
				a[count--] = b[j];
				j--;
			}
		}		
	}
}

int Merge(int a[], int b[], int m, int n)
         {                                              
 /*Worst case is                                                              O(k). where k is n+m
 k is length of array B,                                                                m is no of elements in array A,  n is                           
  no of elements in array b */



                    int i=m, j = n;
                     int k = b.length;
                    while(k>=0 && i>=0)
                       {
                          if(b[j] < a[i]){
                            
                              b[k] = a[i]
                               i--; k--;  
                           }
                          else
                             {
                                   b[k] = b[j];
                                   k--; j--;
                             }
                        }
                    

          }

You can done this by Merge and insertion sort methods.