Leetcode: Merge Sorted Array

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

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Analysis:This question is quite closed to the last step of the merge sort. But the question asks for merging B into A, i.e. in-place merge, instead of merge A and  B into a new array C. 

For instance, for given array A= [1, 3, 5, 7, 9] and B = [2, 4, 6, 8, 10], the final merge array should be A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Naive Solution:
A very straight forward solution is very closed to the last step of the merge sort. First we can copy all elements of the Array A into a new array, aux, then we use two pointers pointing to the starting address of the address aux, and B, compare the value pointed to and move the smaller number into the array A, increase the pointer. Several conditions need to be carefully handled:
1. Empty array: A shouldn't be empty while B is not empty, because A will hold the final merged array. So we only need to check if array B is empty. If yes, return array A directly. This handles when array A and B are both empty as well.

2. If m is not equal to n, i.e, array A and B are not the same length. In that case, we have to handle the trailing numbers. It is relatively easy because we just need to append the trailing numbers into array A. For example, Aux = [1, 3, 5, 7], B = [2, 4, 5, 6, 8, 9], for Aux reaches to the end, the Array A has [1, 2, 3, 4, 5, 5, 6, 7], so we just need to append 8 and 9 into the array.

Code (Java):

public class Solution {
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        // check Array is empty
        if (n == 0) return;
        
        // Allocate a temporary buffer to store m elements in array A
        int[] Aux = new int[m];
        
        // copy elments from array A to Aux
        for (int i = 0; i < m; i++) {
            Aux[i] = A[i];
        }
        
        // merge two arrays into A
        int i = 0;
        int j = 0;
        int k = 0;
        while ((i < m) || (j < n)) {
            if (i == m)              A[k++] = B[j++];
            else if (j == n)         A[k++] = Aux[i++];
            else if (Aux[i] <= B[j]) A[k++] = Aux[i++];
            else                     A[k++] = B[j++];
        }
    }
}

Discussion:
Copying Array A into Aux takes O(m) time. The merge process takes O(m) + O(n) time since each element will be accessed by once. So the total time complexity is O(m+n). Since we need additional m spaces to store the array aux, the space complexity is O(m). 

A Better Solution:
In the naive solution above, we need a temporary array to copy elements of A first. Can we merge into arrays in places, i.e, without allocating a temporary buffer? The answer is yes, we can iterate the array backwards. 

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        // check Array is empty
        if (n == 0) return;
        
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        
        while (i >= 0 && j >= 0) {
            if (A[i] >= B[j]) A[k--] = A[i--];
            else A[k--] = B[j--];
        }
        
        // handle trailing numbers
        while (j >= 0) {
            A[k--] = B[j--];
        }
    }
}

Discussion:
This is a very efficient solution. For the time complexity, we can see that in worst case it needs to scan both A and B, so the complexity is O(m+n). The worst case happens when A = {5, 6, 7, 8} while B = {1, 2, 3, 4}, so we need to move all elements in A into the end and move all elements in B into the front of A. In the best case, the complexity is only O(n). For e.g. A = {1, 2, 3, 4} and B={5, 6, 7, 8}. Then only B will be moved to the trails of A. 

The crux of this question is the loop condition.  Consider why not handle trailing numbers of array A? It means when B reaches to the beginning, the while loop ends. In this case the rest of A was already there and sorted. So we don't need to move A in place...

Summary:
In this post, we learned how to merge two sorted array into one. We discussed two solutions, one naive and one with no space overhead and better time complexity. Be carefully the two pointers solution from the end. It is widely used in sorted array problem.

Update on 9/30/14:

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