merge_sort

#include <iostream>
#include <vector>
using namespace std;

int inver = 0;
void merge(vector<int> &unsorted, int l, int mid, int r, vector<int> &sorted){
    int i = l;
    int j = mid + 1;
    int k = l;
    while(i <= mid && j <= r){
        if(unsorted[i] <= unsorted[j]){
            sorted[k] = unsorted[i++];
        }else{
            sorted[k] = unsorted[j++];
            inver += mid - i + 1;
        }
        k++;
    }

    while(i <= mid){
        sorted[k++] = unsorted[i++];
    }

    while(j <= r){
        sorted[k++] = unsorted[j++];
    }

    for(int i = l; i <= r; i++)
        unsorted[i] = sorted[i];
}

void mergeSort(vector<int> &arr, int left, int right, vector<int> &sort){
    if(left < right){
        int mid = (left + right) >>1;
        mergeSort(arr, left, mid, sort);
        mergeSort(arr, mid  + 1, right, sort);

        merge(arr, left, mid, right, sort);
    }
}

int main(){
    vector<int> test = {5, 4, 7, 69, 30,18, 2, 1};
    vector<int> s(test.size(), 0);

    mergeSort(test, 0, test.size() - 1, s);

    for(auto m:s)
        cout<<m<<" ";
    cout<<endl;
    cout<<inver<<endl;
    return 0;
}