[LintCode] Merge Sorted Array

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

Example

A = [1, 2, 3, empty, empty], B = [4, 5]

After merge, A will be filled as [1, 2, 3, 4, 5]

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 nrespectively.

Analysis: We can just take advantage of the extra space of A to accommodate B.

class Solution {
public:
    /**
     * @param A: sorted integer array A which has m elements, 
     *           but size of A is m+n
     * @param B: sorted integer array B which has n elements
     * @return: void
     */
    void reverse(int A[], int start, int end)
    {
        while(start < end)
        {
            int tmp = A[start];
            A[start] = A[end];
            A[end] = tmp;
            start++;
            end --;
        }
    }
    void mergeSortedArray(int A[], int m, int B[], int n) {
        // write your code here
        if(0 == n) return ;
        int index = m;
        int i = 0, j = 0;
        while(j<n)
        {
            int toFit = index++ % (m+n);
            if(i<m && A[i] < B[j]) A[toFit] = A[i++];
            else A[toFit] = B[j++];
        }
        reverse(A, m,m+n-1);
        reverse(A, 0, m-1);
        reverse(A, 0,m+n-1);
    }
};