Counting inversions in a vector using mergesort c++

Question

The algorithm is returning an off by one error for some of the inputs I send to it. I wrote the merge_sort and inversion_count with array first; which gave back the right number of inversions. Once I transitioned to vectors I receive off by one for the following input: 2 4 1 3 5

A fresh pair of eyes would be appreciated.

vector<int> a;
object o;

length = a.size();
inv = o.count_inversion(a, 0, length-1);



int inversion::merge_and_count(vector<int> vector1, int alpha, int omega)
{
    int inversion = 0;
    int mid = (alpha + omega) / 2;
    int i = alpha;
    int j = mid + 1;
    int lastITR = 0;
    vector<int> final(omega - alpha + 1);


while (i <= mid && j <= omega) {
    if (vector1[i] <= vector1[j])
    {
            final[lastITR++] = vector1[i++];
    }
    else
    {
            final[lastITR++] = vector1[j++];
            inversion += mid - i + 1;
    }
}

while (i <= mid)
    {
    {
    final[lastITR++] = vector1[i++];
    }

    while (j <= omega)
    {
    final[lastITR++] = vector1[j++];
    }

    for (int k=0 ; k < omega-alpha+1; k++)
    {
    vector1[k+alpha] = final[k];
    }

return inversion;
}


int inversion::count_inversion(vector<int> vector1, int a, int b)
{
int x, y, z, mid;

if (a >= b)
    {
            return 0;
    }

mid = (a+b)/2;

x = count_inversion(vector1, a, mid);
y = count_inversion(vector1, mid+1, b);
z = merge_and_count(vector1, a, b);

return x + y + z;
}

Answer 1

The one thing likely causing your issue is below (note: I have no idea what you're trying to do, but I don't think it honestly matters):

int inversion::merge_and_count(vector<int> vector1, int alpha, int omega)
// note: pass by *value*, not reference ------^

Clearly you intend to actually modify this vector for the caller, because at the end of your routine:

for (int k=0 ; k < omega-alpha+1; k++)
{
    vector1[k+alpha] = final[k];
}

Essentially, you're building a merged final, then copying it into a vector that is about to be destroyed. The caller-side vector<int> is untouched when this is done, staying the same as it was prior.

Fix this by using a reference:

int inversion::merge_and_count(vector<int>& vector1, int alpha, int omega)
// note: reference -----------------------^

There are some potential problems, but that is likely the one that is giving you grief. Passing by-value into count_inversion should be ok, since it isn't clear you want to modify the caller-vector there, and if this is only counting inversions, you likely don't want to. But merge_and_count needs to use a reference.

Note: Once you learn iterators you'll happily use them for modeling something like this. It makes the code not only cleaner, but automagically allows its use on any sequence container supporting the proper iterator type.