CareerCup

void merge(int[] bigArray, int[] smallArray, int m, int n) {
    // bigArray is supposed to have enough capacity to hold m + n elements.
    int currentIndex = (m + n) - 1;
    int bigArrayIndex = m - 1;
    int smallArrayIndex = n - 1;
    while (currentIndex >= 0) {
        if (bigArray[bigArrayIndex] > smallArray[smallArrayIndex]) {
            bigArray[currentIndex] = bigArray[bigArrayIndex];
            --bigArrayIndex;
        }
        else {
            bigArray[currentIndex] = smallArray[smallArrayIndex];
            --smallArrayIndex;
        }
        --currentIndex;
    }
}

Place 2 pointers at the end of each array and then compare the elements. The bigger one moves at the end of second array and then decrement the pointer which is pointing to big element. Repeat this step till you finish up with all the elements of the array.

Ex: first array 1 2 3 4 5 (n = 5)
Second array 3 5 6 7 8 9 10 (n = 5, m = 2) (As per the question second array size is big enough to hold elements from the first array. Hence size of it is 12)

Now have one pointer to 5 of first array, another pointer to 10.
Compare 5 and 10, move 10 to end of second array (ofcourse have to maintain pointer for this)
Decrement pointer to point to 9 in the second array.
Repeat this step until all the elements are done.

Here when we encounter same element twice while comparing, place that number twice and then decrement pointers of both array to point to prev element

Hope I am clear in explaining the algorithm

int A[m+n], B[n];

size_t i = m - 1, j = n - 1, k = m + n - 1;

while(i >= 0)
{
    if(A[i] > B[j])
    {
        A[k--] = A[i--];
    }
    else
    {
        A[k--] = B[j--];
    }
}

while(j >= 0)
{
    A[k--] = B[j--];
}

public class MergeSortedArrays {
	
	public static void main(String[] args) {
		int[] smallArray = {1, 5, 7, 10};
		int[] bigArray = {2,3,4,6,8,10,0,0,0,0};
		int x = smallArray.length-1;
		int y = bigArray.length-smallArray.length-1;
		int z = bigArray.length-1;
		while(z>=0) {
			if(x<0) {
				bigArray[z] = bigArray[y];
				z--;
				y--;
				continue;
			} else if(y<0) {
				bigArray[z] = smallArray[x];
				z--;
				x--;
				continue;
			}
			if(smallArray[x] > bigArray[y]) {
				bigArray[z] = smallArray[x];
				x--;
			} else {
				bigArray[z] = bigArray[y];
				y--;
			}
			z--;
		}
		for(int i=0;i<bigArray.length;i++) {
			System.out.print(bigArray[i]+" ");
		}
	}

}

Trick is to start from end.

use insertion sort technique

Starting from intuition:
Sol1: For each element a in A, insert a into B. This would be O(n*(n+m))
Sol2: Make the room(N empty cells) at the head of B. Merge(A,B,B) O(n+m + n+m)
Sol2: Let's do it the other way around from Sol2. Merge(A,B,B) starting from their ends.

Check if this code satisfies all the cases:
main()
{
int A[10],B[20];
int m,n;
printf("Enter the number of elements in A: ");
scanf("%d", &m);
printf("Enter array A: ");
for(int i=0;i<m;i++)
scanf("%d", &A[i]);
printf("Enter the number of elements in B: ");
scanf("%d", &n);
printf("Enter array B: ");
for(int i=0;i<n;i++)
scanf("%d", &B[i]);
int i=m-1,j=n-1;
int k=m+n-1;
while((i>=0)&&(j>=0))
{
if(A[i]>B[j])
{
B[k]=A[i];
i--;
k--;
}
else
{
B[k]=B[j];
j--;
k--;
}
}
if(i<0)
for(int x=j;x>=0;x--)
{
B[k]=B[x];
k--;
}
else if(j<0)
for(int x=i;x>=0;x--)
{
B[k]=A[x];
k--;
}
for(int x=0;x<(m+n);x++)
printf("%d ",B[x]);
}

Assuming m, n are the number of elems in a & b respectively.

void merge(int a[], int b[], int m, int n){
	int lenA = m;
	int lenB = n-m;
	int mergeIndex = m+n-1;
	int bIndex = lenB - 1;
	int elemsLeftToMerge = lenA -1;

	while(elemsLeftToMerge >= 0){
		if(a[elemsLeftToMerge] > b[bIndex]){
			b[mergeIndex--] = a[elemsLeftToMerge--];
		}
		else{
			b[mergeIndex--] = b[bIndex--];
		}
	}
}

I know that it's the last step of a merge sort, but it was not allowed to used an extra structure. So the insert made it complicated. Can you provide solutions for this? thanks.

My doubt is, if there is an element in both arrays, whether that element is added to second array or just skipped..?