CareerCup

start scanning both the arrays from end
suppose b is having extra space
after comparing both elements (a[i] & b[i])
place the bigger element at the end of b
and end-- for b

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv)
{
	int *a, *b;
	int c;

	// Number of elements hardcoded to 4
	a = (int*) malloc (sizeof(int) * 4);
	b = (int*) malloc (sizeof(int) * 8);

	int counter = 0;
	// assigning [0,2,4,6] to a
	for(int i = 0; i < 8; i = i+ 2) 
		a[counter++] = i;


	counter = 0;
	// assigning [1,3,5,7] to b
	for(int i = 1; i < 9; i = i+ 2) 
		b[counter++] = i;


	// now perform the sorting
	int lastBIndex = 7;
	int lastElementInBIndex = 3;
	int lastElementInAIndex = 3;

	int elementCount = 0;

	printf("\nMerge sort result\n");

	while(elementCount < 8)
	{
		// look at teh last elemnt in a and b array and choose the bigger one.. put it at b[lastBIndex]

		if (a[lastElementInAIndex] >= b[lastElementInBIndex])
		{
			// a has the bigger element
			b[lastBIndex--] = a[lastElementInAIndex--];
		}

		else if (a[lastElementInAIndex] < b[lastElementInBIndex])
		{
			// b has the bigger element
			b[lastBIndex--] = b[lastElementInBIndex--];
		}

		elementCount++;

	}

	for(int i = 0; i < 8; i++) {
		printf("\ni=%d\n" , b[i]);
	}

	scanf("%d" , &a);
}

/*
Logic: Store both the elements of a and b in b(as it has extra space).
NOw use a for storing the merged elements. Note : Only sizeof(a) elements can be merged at a time 
(after that move the merged elements back into b and repeat the process for the elemnts that are yet to be merged).
Complexity O(n)
Moving/shifting the elements between a and b and withing b are the operations that affects performance. variable tot is used to calculate that. 
*/
#include<iostream>

using namespace std;

int tot=0;

void merge(int *a,int size_a,int *b,int size_b,int *c,int size_c,int *n_a,int *n_b)
{
  int pa=0,pb=0,pc=0;
  assert(pa <=pc);
  assert(pb <= pc);
  
    while(pc<size_c  && pa<size_a && pb<size_b)
    {
        if(a[pa]<b[pb])
        {
           c[pc++]=a[pa++];             
        }       
        else
        {
            c[pc++]=b[pb++];
        }         
    }
    
    while(pc < size_c && pa < size_a)
    {
       c[pc++]=a[pa++];      
    }
    
    while(pc < size_c && pb <size_b )
    {
       c[pc++]=b[pb++];
    }               
        
    *n_a=pa;
    *n_b=pb;
}


void move(int * src,int *dst,int n)
{
     int i=n,j=n;
     
     while(i>0)
     {
       dst[--j]=src[--i];
       tot++;
     }              
}

int main()
{
  int *a; 
  int *b; 
  int i,j;
  int size_a;
  int size_b;
  int pa=0;
  int pb=0;
  
  
  printf("Enter no of elements in a");
  scanf("%d",&size_a);
  a=(int *)malloc(size_a*sizeof(int));
  
  for(i=0;i<size_a;i++)
    a[i]=i*2+1;
  
  printf("Enter no of elements in b");
  scanf("%d",&size_b);
  b=(int *)malloc((size_a+size_b)*sizeof(int));
  
  for(i=0;i<size_b;i++)
    b[i]=i*2;  
  
  
  int moved=0;
  
  // remb points to the remaining elements of the first array to be merged. rema points to the to the remaining elements of the second array to be merged
  int *rema;
  int *remb;
  int size_rema;
  int size_remb;
  
  //store the elements of a and b in the same array b. make sure the smaller array is followed by the larger one for better performance.
  if(size_a > size_b)
  {
      move(a,b+size_b,size_a);      
      remb=b;
      rema=b+size_b;
      size_rema=size_a;
      size_remb=size_b;
  }
  else
  { 
      move(b,b+size_a,size_b);
      move(a,b,size_a);
      remb=b;
      rema=b+size_a;
      size_rema=size_b;
      size_remb=size_a;      
  }
  
  
  
  while(moved<(size_a+size_b))
   {
     merge(rema,size_rema,remb,size_remb,a,size_a,&pa,&pb);

     moved+=pa+pb;
     size_rema-=pa;
     size_remb-=pb;
     
     move(remb+pb,remb+pa+pb,size_remb);
     move(a,remb,pa+pb);     
     
     rema=rema+pa;
     remb=remb+pa+pb;    
         
   }
  
  for(i=0;i<size_a+size_b;i++)
    printf("%d ",b[i]);
  
  printf("\n%d",tot);

  return 0;    
}

Forgot to mention the soln I gave ->

public static int[]  addToArrayInSecond(int[] first, int[] second){
	int f_len = first.length;
	int s_len = second.length;
	int i=f_len-1,j=second.length -first.length-1;	
	while(i>=0 && j>=0){		
		if(first[i] >second[j]){
			second[i+j+1]=first[i];
			i--;
		}else{
			second[i+j+1]=second[j];
			j--;
		}		
	}
		if(j<0){
			while(i>=0){
				second[i]=first[i];
				i--;
			}
	}
	return second;
}

void merge(int[] a, int[] b) {
    int i = 0;
    int j = 0;
    
    while (i < a.length) {
        if (a[i] <= b[j]) {
            // insert a at b[j]. shift b[j] -> b[j+1]
            int tmp = b[j+1];
            for (int k = b.length-1; k > j; k--) {
                b[k] = b[k-1];
            }            
            i++;
        } else {
            j++;
        }
    }
}

void merge(int[] a, int[] b) {
    int i = 0;
    int j = 0;
    
    while (i < a.length) {
        if (a[i] <= b[j]) {
            // insert a at b[j]. shift b[j] -> b[j+1] and so on
            for (int k = b.length-1; k > j; k--) {
                b[k] = b[k-1];
            }
            b[j] = a[i];

            i++;
        } else {
            j++;
        }
    }
}