[LeetCode] Merge Sorted Array

Link : 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 to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Analysis:
Many options:
1) add element from left to right, and move the followings back. possible but wasting operations
2) move all of A's element all the way to its end(to m+n-1), and merge A's content and B'content from A's very beginning(A[0]). Possible, but there is a symmetric option, that's option 3)
3) merge A and B, and store the merged one starting from A's end(A[m+n-1]), no need to move A's element at firs t or during merging anymore. Because A is sorted and A's last not-yet-merged element will never be covered by the sorted element. Try it yourself and see!

 class Solution3 {
    public:
    void merge(int A[], int m, int B[], int n) {
        if(n==0)
        return;
        int sum = m + n;
        int i=m-1;
        int j=n-1;
        for(int k=sum-1; k>=0; k--)
        {
            if(i>=0&&j>=0)
            A[k] = A[i]>B[j]?A[i--]:B[j--];
            else if(i==-1)//A is finished
            A[k] = B[j--];
            else // B is finished
            break;// or could be A[k] = A[i--];but no need
        }
    }
};