counting_inversions.cpp

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

int merge(vector<int>& v, int left, int delim, int right) {
    int inv_counter = 0;
    int i = left;
    int j = delim;
    int k = 0;
    vector<int> aux(right-left+1);
    while (i < delim and j <= right) {
        if (v[i] <= v[j]) {
            aux[k] = v[i];
            ++i;
        }
        else {
            aux[k] = v[j];
            ++j;
            inv_counter += (delim-i)+1;
        }
        ++k;
    }
    while (i < delim) {
        aux[k] = v[i];
        ++i;
        ++k;
    }
    while (j <= right) {
        aux[k] = v[j];
        ++j;
        ++k;
    }
    for (int l = left; l <= right; ++l) {
        v[l] = aux[l-left];
    }
    return inv_counter;
}

int merge_sort_impr(vector<int> v, int left, int right) {
    if (left >= right) return 0;
    int inv_counter = 0;
    int middle = (left+right) / 2;
    inv_counter += merge_sort_impr(v, left, middle);
    inv_counter += merge_sort_impr(v, middle+1, right);
    inv_counter += merge(v, left, middle, right);
    return inv_counter;
}

int main() {
  int vsize;
	while (cin >> vsize) {
		vector<int> v(vsize);
		for (int i = 0; i < vsize; ++i) cin >> v[i];
		cout << merge_sort_impr(v, 0, vsize-1) << endl;
	}
}