Error when counting inversions in a sequence

Hello,

I want to code a program that counts all the inversions in a sequence of integers. An inversion is a pair of indices i,j such that i<j but xi > xj.

I have made a modification of merge sort which has a mistake somehwere that I am not able to see. I have tried to put couts in the functions and I think it has to do with indices but I can't really find the problem.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <vector>
using namespace std;

int all_together_now(vector<int>& v, int e, int m, int d) {
    vector<int> aux(d-e+1);
    int count = 0;
    int o = m-e;
    int i = e;
    int j = m+1;
    int k = 0;
    while(i<=m and j<=d) {
        if (v[i] > v[j]) {
           aux[k] = v[j];      ++k; ++j;      
           count += o-i;           
        }
        else {aux[k] = v[i]; ++k; ++i;}
    }
    while (i<=m) {aux[k] = v[i]; ++k; ++i; }
    while (j<=d) {aux[k] = v[j]; ++k; ++j; }
    for (int p = 0; p < d-e+1; ++p) v[e+p] = aux[p];
    return count;    
}

int no_inv(vector<int>& v, int e, int d) {
    if (e < d) {
         int m = (e+d)/2;
         return no_inv(v, e, m) + no_inv(v, m+1, d) + all_together_now(v, e, m, d);
    }
    return 0;
}

int main () {
    int n;
    while (cin >> n) {
          vector<int> V(n);
          for (int i = 0; i < n; ++i) cin >> V[i];
          cout << no_inv(V, 0, V.size()-1) << endl;
    }     
}


Thanks a lot have a nice day
Topic archived. No new replies allowed.