88. Merge Sorted Array

https://leetcode.com/problems/merge-sorted-array/

1. Use STL sort():

//4 ms    9.1 MB
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i = 0; i < n; i++){
            nums1[m+i] = nums2[i];
        }
        sort(nums1.begin(), nums1.end());
    }
};

2. Use merge sort:

//8 ms    13.2 MB
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i = 0; i < n; i++){
            nums1[m+i] = nums2[i];
        }
        //sort(nums1.begin(), nums1.end());
        mergeSort(nums1);
    }
private: 
    void merge(vector<int>& arr, int l, int m, int r){
        int n1 = m - l + 1;
        int n2 = r - m;
        int i, j, k;
        vector<int> L;
        vector<int> R;
        for(i = 0; i < n1; i++){
            L.push_back(arr[l+i]);
        }
        for(j = 0; j < n2; j++){
            R.push_back(arr[m+1+j]);
        }
        i = 0;
        j = 0;
        k = l;
        while(i < n1 && j < n2){
            if(L[i] <= R[j]){
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        while(i < n1){
            arr[k] = L[i];
            i++;
            k++;
        }
        while(j < n2){
            arr[k] = R[j];
            j++;
            k++;
        }
    }
    void mergeSort(vector<int>& arr, int l, int r){
        if(l < r){
            int m = l + (r - l) / 2;
            mergeSort(arr, l, m); 
            mergeSort(arr, m + 1, r); 
            merge(arr, l, m, r); 
        }
    }
    void mergeSort(vector<int>& arr){
        int n = arr.size();
        mergeSort(arr, 0, n-1);
    }
};