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]

Solution:

(1) 第一种方法, O(n2)复杂度，因为每次对比当前的两个数组的索引对应的两个值，如果B里面的小，这时需要插入进入数组，整体右移动数组，然后插入，

(2) 可以利用数组长度正好等于 m + n ， 把大的值直接放到最右边，这样可以省去移动操作。

class Solution:
    """
    @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
    """
    def mergeSortedArray(self, A, m, B, n):
        # write your code here
        i, j, k = m - 1, n - 1, m + n - 1
        while i >= 0 and j >= 0:
            if A[i] > B[j]:
                A[k] = A[i]
                k -= 1
                i -= 1
            else:
                A[k] = B[j]
                k -= 1 
                j -= 1

        while i >= 0:
            A[k] = A[i]
            k -= 1
            i -= 1
        while j >=0:
            A[k] = B[j]
            k -= 1
            j -= 1