CareerCup

This can be done by comparing the last elements of both array and place the higher one at the end of the second array. Below is the C code with complexity O(m+n),

int a[] = { 1, 4, 6};
int b[] = { 2, 3, 5, 7, 8, 0, 0, 0};

        int size_a = sizeof(a)/sizeof(int);
        int size_b = sizeof(b)/sizeof(int) - size_a;
        int index_a, index_b, index_c;
        int i = 0;
        index_a = size_a - 1;
        index_b = size_b - 1;
        index_c = size_a + size_b - 1; //Result Index

        while(index_a>=0 && index_b>=0){
                if(a[index_a] > b[index_b]){
                        b[index_c] = a[index_a];
                        index_a--;
                }else{
                        b[index_c] = b[index_b];
                        index_b--;
                }
                index_c--;
        }
        while(index_a >= 0){
                b[index_c] = a[index_a];
                index_a--;
                index_c--;
        }

        while(index_b >= 0){
                b[index_c] = b[index_b];
                index_b--;
                index_c--;
        }

        for(i=0; i<size_a+size_b; i++){
                printf("%d, ", b[i]);
        }

Is resultant array space allocated seperately from the two sorted arrays?

two arrays:
first 1 2  3 4 5 6 7
second 2 6 7
1. have two pointers first_pointer and second_pointer and it is pointing to first and second respectively.
2. compare them and put it in the longest array.
    compare(1, 2) first array[] = 1 first_pointer pointing to 2 now.
    compare(2, 2) first array[] = 1 2 2 first_pointer pointing to 3 & second_pointer to 6
    compare(3, 6) first array[] = 1 2 2 3 first_pointer pointing to 4 & second_pointer to 6
so on.....

#include<iostream>
using namespace std;
#define Size1 7
#define Size2 12

int main(){				

	int arr1 [] ={-3,-1,4,4,6,11,13};
	int arr2[] ={-2,0,11,48,49,0,0,0,0,0,0,0};              // works for -ve as well as +ve integers as well as 0.	Also works for duplicate values .
	int low1 =0;
	int high1 = Size2-Size1-1;   								// the index of last element in array2 .
	int copyLow1= low1;
	int copyHigh1 = high1;
	
	for(int i=0; i<Size1;){			
		int num1 = arr1[i];		
		low1= copyLow1;
		high1= copyHigh1;		
		
		while(low1<=high1){										// find the index in the senond array to insert the ith element from first array
		
			int mid = (low1+high1)/2;							
			
			if(arr2[mid] > num1)
				high1 =mid-1;
			else
				low1 = mid+1;				
		
		}
		
		if(low1>copyHigh1){										// the element in array1 is greater than the last element of array2 so now fill array2 with array1
			for(int z = copyHigh1+1;z<Size2;z++)
				arr2[z] = arr1[i++];
			
			break;
		
		}		
		
		int low2 = i;
		int high2 = Size1-1; 								// last index of 1st array .
		int compareWith = arr2[low1];
		
		while(low2<=high2){										// to calculate how many numbers from array1 can be shifted to array2 at once .
		
			int mid = (low2+high2)/2;
			if(arr1[mid]>=compareWith)
				high2 = mid -1;
			else
				low2 = mid+1;			
		
		}				
		
		int noOfShifts = low2 - i ;					// noofshifts = number of elements from array1 which will be moved to array2 .
		
		for(int j = copyHigh1;j>=low1;j--){         // shift array2 elements by the noofshift calculated
		
			arr2[j+noOfShifts] = arr2[j];
			
		}
		for(int k =0 ;k<noOfShifts;k++){ 			// insert the array1 elements into array2 .
		
			arr2[low1+k] = arr1[i+k];
		}
		
		i = i+noOfShifts;
		copyLow1 = copyLow1 + noOfShifts;
		copyHigh1 = copyHigh1 + noOfShifts;		
		
	}
	
	for(int i =0;i<Size2;i++)						// Print the result
		cout<<arr2[i]<<" ";
	
	return 0;
}

Use merge sorting