Merge Sort

Verified here: https://www.geeksforgeeks.org/problems/merge-sort/1

class Solution {
  public:
    void merge(vector<int>& arr, int l, int m, int r) {
        int total = r-l+1;
        int n1 = m-l+1;
        int n2 = total-n1;
        
        vector<int> left;
        vector<int> right;
            
        for (int i = l; i <= r; i++) {
            if (i <= m) {
                left.push_back(arr[i]);
            } else {
                right.push_back(arr[i]);
            }
        }
        
        int start = l;
        int i = 0;
        int j = 0;
        
        while(i < n1 && j < n2) {
            if (left[i] < right[j]) {
                arr[start] = left[i];
                i++;
            }else {
                arr[start] = right[j];
                j++;
            }
            start++;
        }
        while(i < n1) {
            arr[start] = left[i];
            i++;
            start++;
        }
        
        while(j < n2) {
            arr[start] = right[j];
            j++;
            start++;
        }
    }
    void mergeSort(vector<int>& arr, int l, int r) {
        // code here
        if (l < r) {
            int m = l+(r-l)/2;
            mergeSort(arr, l, m);
            mergeSort(arr, m+1, r);
            merge(arr, l, m, r);
        }
    }
};