CareerCup

The idea is merging from the back of the b array so the write op of the merge is never interfered with read op from b

int i_a = a.size() - 1;
int i_b = b.size() - 1;
int i_ab = a.size() + b.size() - 1;
	
for ( ; i_a >= 0 && i_b >=0; )
    if (a[i_a] > b[i_b])  b[i_ab--] = a[i_a--];
    else b[i_ab--] = b[i_b--];	
	
if (i_a > 0) {
    for (;i_a >=0;)
        b[i_ab--] = a[i_a--]; 
} else  { // There is nothing to do if i_b > 0 as we merge onto b
}

We just need to merge from the end. Here is my python solution.

def merge(xs, xs_size, ys, ys_size):
    """Merge two arrays in the first one

    Example:
        >>> merge([1, 3, 5, 0, 0, 0], 3,
        ...       [2, 4, 6], 3)
        [1, 2, 3, 4, 5, 6]
        >>> merge([1, 0, 0, 0], 1,
        ...       [0, 2, 3], 3)
        [0, 1, 2, 3]
        >>> merge([0, 2, 3, 0], 3,
        ...       [1], 1)
        [0, 1, 2, 3]
    """
    i, j = xs_size, ys_size
    while i + j > 0:
        if j <= 0:
            i -= 1
            xs[i + j] = xs[i]
        elif i <= 0:
            j -= 1
            xs[i + j] = ys[j]
        else:
            if xs[i - 1] > ys[j - 1]:
                i -= 1
                xs[i + j] = xs[i]
            else:
                j -= 1
                xs[i + j] = ys[j]
    return xs


if __name__ == '__main__':
    import doctest
    doctest.testmod()

It can be done in one loop.

int i_a = a.size() - 1;
int i_b = b.size() - 1;
int i_ab = a.size() + b.size(
while (i_a >= 0) {
    if (i_b < 0 || a[i_a] >= b[i_b]) {
        b[i_ab--] = a[i_a--];
    } 
    else {
        b[i_ab--] = b[i_b--];
    }
}

public static int[] inplaceSort(int x[], int y[]) {
        int endIndex = x.length-1;
        int xIndex = y.length-1;
        int yIndex = xIndex;
        // Starting at the end of x iterate backwards putting each value in it's place
        for (int i=endIndex; i>=0; i--) {
            System.out.println("Comparing "+x[xIndex]+" and "+y[yIndex]);
            //find the max value between x[xIndex] & y[yIndex]
            if (x[xIndex] > y[yIndex]) {
                System.out.println("x["+xIndex+"]("+x[xIndex]+") > y["+yIndex+"]("+y[yIndex]+")");
                x[i] = x[xIndex];
                xIndex--;
                if (xIndex < 0 && i>0) {
                    x[0]=-1;
                    xIndex=0;
                }
            } else {
                System.out.println("x["+xIndex+"]("+x[xIndex]+") <= y["+yIndex+"]("+y[yIndex]+")");
                x[i] = y[yIndex];
                yIndex--;
                if (yIndex < 0 && i>0) {
                    y[0] = -1;
                    yIndex = 0;
                }
            }
        }
        return x;
    }

Starting from the last element of b and going towards the first, we apply a merge similar to the merge step of mergeSort.

If B has moved completely and A still has elements, move the remaining elements of A to B.
Otherwise, no need to move anything. B elements are already there!

public void mergeSorted(int[] a, int[] b){
    
    //start from the end of b
    //kind of merge sort step of mergeSort algorithm
    int current = b.length-1;
    int helperA = a.length-1;
    int helperB = b.length/2-1;
    while (helperA>=0 && helperB>=0){
        if (arr[helperA]>=arr[helperB])
        {
            b[current] = arr[helperA];
            helperA--;
        }
        else{
            b[current] = arr[helperB];
            helperB--;
        }
        current--;
    }
    
    if (helperA>0)
    {
        while(helperA>=0)
            b[current--] = arr[helperA--];
    }
    //else do nothing, b elements are already there
}

-(NSArray *)mergeFirstSortedArray:(NSArray *)firstArray withSecondSortedArray:(NSArray *)secondArray{
    NSMutableArray *secondMutable = [secondArray mutableCopy];
    NSInteger secondArrayCount = [secondArray count];
    NSInteger currentIndex = 0;
    for (NSNumber *num in firstArray) {
        while (currentIndex < secondArrayCount) {
            if ([num integerValue] < [secondMutable[currentIndex] integerValue]) {
                [secondMutable insertObject:num atIndex:currentIndex];
                currentIndex++;
                break;
            }
            else{
                currentIndex++;
            }
        }
    }
    return secondMutable;
}

static void Merge(int[] a, int[] b) // assumption: length of b is twice bigger than length of a
{
    int i = a.Length - 1;
    int j = a.Length - 1;
    
    for (int p = b.Length - 1; p >=0; p--)
    {
        if (i >= 0 && (j < 0 || a[i] > b[j]))
        {
            b[p] = a[i--];
        }
        else
        {
            b[p] = b[j--];
        }
    }
}

void merge(int[] a, int[] b, int length){
	assert(a.length == length);
	assert(b.length == 2*length);
	int i = length-1;
	int j = length-1;
	for(int k = 1; k<=length*2; k++){
		a[i] > b[j]? i--:j--;
		b[length*2-k] = a[i] > b[j]? a[i]: b[j];
	}
}

JavaScript

}}}
function merge(left, right){
var result = [];
while(left.length && right.length){
if(left[0] <= right[0]){
result.push(left.shift());
}else{
result.push(right.shift());
}
}

while(left.length){
result.push(left.shift());
}
while(right.length){
result.push(right.shift());
}

return result;

}
}}}

#Seems to be fairly straightforward with Ruby
def merge_arrays a, b

(a | b).sort

end

#Seems to be fairly straightforward with Ruby 
def merge_arrays a, b
	(a | b).sort
end

a = [1, 3, 5, 5]
b = [2, 4, 6, 6]
def merge_sorted_arr(a, b):
    index = 0
    while a:    
        if b[index] > a[0]:
            b.insert(index, a.pop(0))
        index += 1
    return b

Java solution. Took about 15 mins, including testing edge cases. Code could be improved.

public static int[] merge(int[] a, int b[]) {
		
		if(a.length == 0) return b;
		if(b.length == 0) return a;
		
		int[] result = new int[a.length + b.length];
		
		int posA = 0, posB = 0;
		for(int i = 0; i < result.length; i++) {
			
			if(posA >= a.length && posB < b.length) {
				result[i] = b[posB];
				posB++;
			}
			else if(posB >= b.length && posA < a.length) {
				result[i] = a[posA];
				posA++;
			}
			else {
				if(a[posA] <= b[posB]) {
					result[i] = a[posA];
					posA++;
				}
				else {
					result[i] = b[posB];
					posB++;
				}
			}
		}
		
		return result;
	}