# merge sorted array
###### tags: `array`

範例：
輸入：
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
輸出：
[1,2,2,3,5,6]

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        //兩個vector都已經排序過
        //比較兩個vector的值然後插入
        //因為nums1有空格了從後面開始放會更好
        int i = m - 1;  //nums1的尾端
        int j = n - 1;  //nums2的尾端
        int k = m + n -1;   //合併後的尾端
        if(nums2.empty()){
            return ;
        }
        if(nums1.empty()){
            for(int k = 0; k < nums2.size(); k++){
                nums1.push_back(nums2[k]);             
            }
        }

        while(i >= 0 && j >= 0){
            if(nums1[i] >= nums2[j]){   
                nums1[k] = nums1[i];    //升序
                k--;
                i--;
            }else{
                nums1[k] = nums2[j];
                k--;
                j--;
            }
        }
        //如果nums2還有沒被放到的元素代表剩下的都小於nums1了 所以按照順序放入 因為是已經排序好的
        while(j >= 0){
            nums1[k] = nums2[j];
            k--;
            j--;
        }
    }
};

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    // 從尾端開始放
    let rear = m + n - 1;
    let i = m - 1;
    let j = n - 1;
    while(i >= 0 && j >= 0){
        if(i >= 0 && j >= 0 && nums1[i] > nums2[j]){
            nums1[rear] = nums1[i];
            i--;
            rear--;
        }else{
            nums1[rear] = nums2[j];
            j--;
            rear--;
        }
    }

    while(i >= 0){
        nums1[rear] = nums1[i];
        i--;
        rear--;
    }
    while(j >= 0){
        nums1[rear] = nums2[j];
        j--;
        rear--;
    }

    return nums1;
};