void merge(vector<int>& arr, int l, int m, int r) {
    vector<int> temp;
    int i = l;
    int j = m + 1;

    // Merge the two sorted halves into temp
    while (i <= m && j <= r) {
        if (arr[i] < arr[j]) {
            temp.push_back(arr[i++]);
        } else {
            temp.push_back(arr[j++]);
        }
    }

    // Copy any remaining elements
    while (i <= m) temp.push_back(arr[i++]);
    while (j <= r) temp.push_back(arr[j++]);

    // Copy temp back to arr
    for (int k = l; k <= r; k++) {
        arr[k] = temp[k - l];
    }
}

void mergeSort(vector<int>& arr, int l, int r) {
    if (l < r) {  // Corrected condition
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

Merge Sort Analysis Table