Counting Inversions (CTCI)

Problem: Counting Inversions

long long merge(vector<int> *a, int st, int mid, int ed)
{
    vector<int> v(ed-st+1);
    long long cnt=0;
    int i=st, j=mid+1, vi=0;
    while(i<=mid && j<=ed)
    {
        if(a->at(i) <= a->at(j))
            v[vi++] = a->at(i++);
        else 
        {
            cnt += mid-i+1;
            v[vi++] = a->at(j++);
        }
    }
    while(i <= mid)
        v[vi++] = a->at(i++); 
    while(j <= ed)
        v[vi++] = a->at(j++);
    for(int i=0;i<vi;i++)
        a->at(st++) = v[i];
    
    return cnt;
}

long long mergeSort(vector<int> *a, int st, int ed)
{
    if(st>=ed) return 0;
    long long cnt=0;
    int mid = st + (ed-st)/2;
    cnt += mergeSort(a, st, mid);
    cnt += mergeSort(a, mid+1, ed);
    cnt += merge(a, st, mid, ed);
    return cnt;
}

long long count_inversions(vector<int> a) {
   int al = a.size();
   return mergeSort(&a, 0, al-1); 
}

int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        int n;
        cin >> n;
        vector<int> arr(n);
        for(int arr_i = 0;arr_i < n;arr_i++){
           cin >> arr[arr_i];
        }
        cout << count_inversions(arr) << endl;
    }
    return 0;
}