CareerCup

int A[5] = {1,3,8,9};
int B[9] = {2,4,5,6,7,0,0,0,0}; // last four as place holders for the merge

// start from the end of the larger array;
int idx = 8;
// we also need the indices of the largest elements in both arrays
int idx_a = 3, idx_b = 4;

while (idx_a >= 0) { // done when A has been traversed
    if (idx_b < 0 || A[idx_a] > B[idx_b]) { // if elements of b are exhausted
        B[idx] = A[idx_a];
        idx_a--;
    }
    else {
        B[idx] = B[idx_b];
        idx_b--;
    }
    idx--;
}

Instead of get rid of the front spaces. We can avoid having the space by calculate the merged size in advance, say k. Then, begin your result index at k-1 th of the larger array. Doing will left no space in the front and guarantee no data element in the larger array being overridden by the data from the smaller array (in case when all element in the first array are greater than second array).

copy the first array into the empty space on the second and then do a quick sort, would take nlogn and quicksort does not take extra space.

comments?

// assuming a is the larger array
void Merge(int[] a, int[] b, int m, int n)
{
int k = m + n - 1;
int curM = m - 1;
int curN = n - 1;

while (curM >= 0 && curN >= 0)
{
if (a[curM] >= b[curN])
{
a[k--] = a[curM--];
}
else if (a[curM] < b[curN])
{
a[k--] = b[curN--];
}
}

while (curN >= 0)
{
array[k--] = b[curN--];
}
}

move all elements in 2nd array towards right and do merging

Assuming that the second array has extra empty space of the exact size as array 1, we can appraoch this problem in a smart way: start merging from Right to left side, i.e.

1. compare the last elements in both the arrays, whichever is greater, add it to the end of second array (which has extra space).
2. similarly keep moving towards smaller elements & add them from right to left in the second array.
3. Exit when all elements in array one are traversed

Using the above approach, no additional space is required. Secondly, when first array is completely traversed, automatically all the elements will be sorted in array 2.

package com.dev.interview;

public class MergeTwoArrays {


	public static void main(String[] args){
		int arr[] = {1,2,54,76,100,0,0,0};
		int brr[] = {1,5,65};
		int l1 = arr.length -1;
		int l2 = brr.length -1;
		int x = 4;
		int y = 2;
		int k = 7;
		while(x>=0){
			//validation
			if(x<0 || y<0 || k<0){
				break;
			}
			
			if(arr[x] >  brr[y]){
				arr[k] = arr[x];
				k--;
				x--;
			}
			if(arr[x] <=  brr[y]){
				arr[k] = brr[y];
				y--;
				k--;
			}
			
		}
		
		//printing the output
		for (int i = 0; i < arr.length; i++) {
			System.out.println(" " + arr[i]);
		}
	}


}