CareerCup

#include <stdio.h>
void merge(int* pA, int* pB, int szA, int szB)
{
	int i=0,j=0,k=0;
	/*
	First Assemble all -1s in the last of the array 
	preserving the array sorted.
	*/
	while((i<szA)&&(j<szA))
	{
		while((i<szA)&&(pA[i] != -1)) i++;
		while((j<szA)&&(j<i)) j++;
		while(pA[j]==-1) j++;
		if((j<szA)&&(i<szA))
		{
			int temp = pA[i];
			pA[i]=pA[j];
			pA[j]=temp;
		}
	}
	i=szA-szB-1;
	j=szB-1;
	k=szA-1;
	/*merge from back side*/
	while((k>=0)&&((i>=0)||(j>=0)))
	{
		if(i<0)
		{
			pA[k]=pB[j];
			j--;
		}
		else if(j<0)
		{
			pA[k]=pA[i];
			i--;
		}
		else if(pA[i]<pB[j])
		{
			pA[k]=pB[j];
			j--;
		}
		else
		{
			pA[k]=pA[i];
			i--;
		}
		k--;
	}
}
int main()
{
	int A[]={-1,-1,8,19,-1,-1,-1,31,-1,38,65,-1,85,-1,-1,110,150,-1};	
	int B[]={24,51,90,130,140,180,190,220,250,260};
	int i=0;
	merge(A,B,sizeof(A)/sizeof(int),sizeof(B)/sizeof(int));
	while(i<(sizeof(A)/sizeof(int)))
	{
		printf("[%d]",A[i]);
		i++;
	}
	printf("\n");
}

Time O(n), space O(1)

<pre lang="" line="1" title="CodeMonkey68729" class="run-this">#include <stdio.h>

void merge(int A[], unsigned int lA, int B[], unsigned int lB)
{
int i = 0, j = 0, k = 0;
while (k < lA) {
while (A[i] < 0)
i++;
if (i == lA)
A[k++] = B[j++];
else if (j == lB)
A[k++] = A[i++];
else if (A[i] < B[j])
A[k++] = A[i++];
else
A[k++] = B[j++];
}
}

int main()
{
int A[] = { -1, -1, 8, 19, -1, -1, -1, 31, -1, 38, 65, -1, 85, -1, -1, 110, 150, -1};
int B[] = {24, 51, 90, 130, 140, 180, 190, 220, 250, 260};
int i = 0;
merge(A, sizeof(A) / sizeof(int), B, sizeof(B) / sizeof(int));
while (i < (sizeof(A) / sizeof(int))) {
printf("[%d]", A[i]);
i++;
}
printf("\n");
}
</pre><pre title="CodeMonkey68729" input="yes">
</pre>

It seems same as its trivial counterpart. Start merging arrays from the back, means start comparing from the highest elements of both arrays.

1) i = m-1 and j = k = n-1.
while(A[j]==-1) j--

2) run loop till k>=0

3) if(A[j] == B[i]) A[k] = A[k-1] = A[j];
k = k-2; i--; while(A[j]==-1) j--;

4) else if(A[j] > B[j]) A[k] = A[j];
k--; while(A[j]==-1) j--;

5) else A[k] = B[i];
k--; i--;

Using a deque (to keep track of sorted index of -1), array A can be rearranged such that all -1s are at end, and the rest are sorted. It takes O(n) time.

Now, merge from back.

IMO, the solutions above are O(n+m) time.

<pre lang="" line="1" title="CodeMonkey88818" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void merge(int[] big, int[] small) {
if (big == null || small == null) {
return;
}

// Shift all positive numbers in bigger array to right. keep them sorted.
for (int i = big.length - 1, j = i; j >= small.length; i--) {
if (big[i] > 0) {
big[j--] = big[i];
}
}

// Merge till the small array is exhausted.
for (int i = 0, pBig = small.length, pSmall = 0; pSmall < small.length; i++) {
if (pBig >= big.length) {
big[i] = small[pSmall++];
} else {
big[i] = big[pBig] <= small[pSmall] ? big[pBig++] : small[pSmall++];
}
}
}

public static void main (String[] args) throws java.lang.Exception {
int[] big = {2, -1, 7, -1, 10, -1, 11, -1, 18, -1, 22, -1, 24, -1, 27, -1, 29};
int[] small = {4, 13, 24, 27, 28, 28, 30, 30};
System.out.println(Arrays.toString(big));
System.out.println(Arrays.toString(small));
merge(big, small);
System.out.println(Arrays.toString(big));
}
}

</pre><pre title="CodeMonkey88818" input="yes">
</pre>

void mergeArrays(int* a, int sizeOfa, int* b, int sizeOfb)
{
    int i = sizeOfa - 1;
    int j;
    int x = i;
    
                
    while (a[i] != -1 && i >=0) {
        i--;
        x--;    
    }   
        
    while (i >= 0) {
        while (a[i] == -1)
            i--;

        if (i >= 0) {
            exchange(a, i, x);
            i--;
            x--;    
        }            
    }

    i = x + 1;
    x = 0;
    j = 0;
    
    while (j < sizeOfb && i < sizeOfa) {
        if (a[i] <= b [j]) {
            exchange(a, x, i);
            x++;
            i++;
        }
        else {
            a[x] = b[j];
            x++;
            j++;                
        }
    }
    
    while (j < sizeOfb) {
        a[x] = b[j];
        x++;
        j++;                
    }
       
}

A clean working Python version: ideone.com/V77A5