Problem

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Solution

The key to solve this problem is moving element of A and B backwards. If B has some elements left after A is done, also need to handle that case. The takeaway message from this problem is that the loop condition.

Solution 1

In this case We have two arrays A and B, but array A have m elements to merge, and m+n placeholders for all elements.

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
 
        while(m > 0 && n > 0){
            if(A[m-1] > B[n-1]){
                A[m+n-1] = A[m-1];
                m--;
            }else{
                A[m+n-1] = B[n-1];
                n--;
            }
        }
 
        while(n > 0){
            A[m+n-1] = B[n-1];
            n--;
        }
    }
}

Memory O(0) (uses only arrays what we have), Steps: O(m+n) - linear

Solution 2

public static int[] merge(int[] a, int[] b) {
    int[] answer = new int[a.length + b.length];
    int i = a.length - 1, j = b.length - 1, k = answer.length;

    while (k > 0)
        answer[--k] =
                (j < 0 || (i >= 0 && a[i] >= b[j])) ? a[i--] : b[j--];
    return answer;
}

Memory O(n); Steps: O(m+n)

Solution 3

 

public void merge(int A[], int m, int B[], int n) {
	int i = m - 1;
	int j = n - 1;
	int k = m + n - 1;
 
	while (k >= 0) {
		if (j < 0 || (i >= 0 && A[i] > B[j]))
			A[k--] = A[i--];
		else
			A[k--] = B[j--];
	}
}

Memory O(1); Steps: O(m+n)