Trouble implementing Mergesort algorithm in c++, syntax of vectors

Question

I'm trying to implement mergesort in cpp, I'm having some trouble with the proper syntax with vectors, in particular the part inside the for loop where I'm merging the elements. Some help would be appreciated. My code so far gives the wrong output. Also, I was wondering if this code could be modified to count inversions as well, everytime I go in the else case, inversions increase but it's missing corner cases. I tried doing the v[i] = left[i1] as v.insert(v.begin() + i, left.at(i1)), which also did not work, I'm in general confused about the [] operator for vectors, how is it different than array [] operator?

#include <bits/stdc++.h>

using namespace std;

void mergeSort(vector<int>& v) {
    if(v.size() > 1) {
        vector<int> left(v.begin(), v.begin() + v.size()/2);  
        vector<int> right(v.begin() + v.size()/2, v.end());

        mergeSort(left);
        mergeSort(right);

        int i1 = 0;
        int i2 = 0;

        for(int i = 0; i < v.size(); i++) {
            if(i2 >= right.size() || (i1 < left.size() && left[i] < right[i])) {
                v[i] = left[i1]; i1++;
            } else {
                v[i] = right[i2]; i2++;
            }
        }       
    }   
}

int main() {
    vector<int> v = {22, 18, 12, -4, 58, 7, 31, 42};
    mergeSort(v);
    for(auto i = v.begin(); i != v.end(); i++) cout << *i << endl;
    return 0;
}

[See this](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c) — PaulMcKenzie, Dec 24 '19 at 14:25
`operator[]` on a vector is just used to access elements in the `vector`'s array, same as an array's `[]` — ChrisMM, Dec 24 '19 at 14:29
ChrisMM for some reason, sometimes, it does not behave correctly when I assume they are same, I can't quite recall but at times it gives me trouble, it was about a month ago when I faced that issue, maybe I was just bad at the language back then, thanks anyway! — Xgh05t, Dec 24 '19 at 14:47
@gh05t if you find any of the answers useful, please accept it to close the question — Steyrix, Dec 24 '19 at 14:59
@ChrisMM I just added another question [link](https://stackoverflow.com/questions/59487483/different-answers-if-i-use-vector-instead-of-array-while-counting-inversions-wh?noredirect=1#comment105149767_59487483) It's a case where vector behaves a little different than an array and one of the reasons why I have confusions sometimes, have a look see if you find the time — Xgh05t, Dec 26 '19 at 14:05

Steyrix · Accepted Answer · 2019-12-24T15:21:04.163

1

I think your condition is wrong (you comparing elements of vectors with index i), try this (I also added check for inversions, as you asked). I just changed names of indexes from i2 and i1 to r and lrespectively.

for (int i = 0; i < v.size; i++) {
    if (r < right.size() && (right[r] <= left[l] || l >= left.size)) {
        if (right[r] < left[l]) inversions++; 
        v[i] = right[r++];  
    } else {
        v[i] = left[l++];
    }    
}

edited Dec 24 '19 at 15:21

answered Dec 24 '19 at 14:38

Steyrix

2,796
1
9
23

It actually works, I accidentally used i++ instead of i1++, small mistake on my part, but your right on! – Xgh05t Dec 24 '19 at 14:49
Are you sure that covers inversions in all cases? I'm having trouble visualizing atm, but I've been at work all day, can't think properly – Xgh05t Dec 24 '19 at 15:01
@gh05t I am not sure (writing code without ability to test it currently), but I edited my answer (only the inversions count). Please test it out. You can find good explanation on how to count inversions here https://www.geeksforgeeks.org/counting-inversions/ – Steyrix Dec 24 '19 at 15:14
I made one more edit, please note that `inversions` should be a global variable – Steyrix Dec 24 '19 at 15:22
I think the inversions are not right at the moment, I will comment after I think about it a while, as for using global variable, I instead used a referenced int ```int& inv``` and I think it's off by a few currently – Xgh05t Dec 24 '19 at 15:25
@gh05t ok, let me know if you find out :) – Steyrix Dec 24 '19 at 15:28
I finally figured it! you can do ```inv += r``` in the first block or ```inv += left.size() - l``` in the second, the issue turned out to be in the if condition I had to do ```if(r >= right.size() || (l < left.size() && left[l] <= right[r]))``` to be more specific ```left[l] <= right[r]```, it merged correctly either way, but couldn't count inversions correctly that way. – Xgh05t Dec 26 '19 at 14:08

score 0 · Answer 2 · answered Dec 24 '19 at 14:38

Your condition is wrong. You need to use the i1 and i2 indexes because i quickly goes beyond the size of right (I checked this with a debugger, you should use it as well!) Here my full solution and some additional tests:

//#include <bits/stdc++.h>
#include <vector>
#include <iostream>

using namespace std;

void mergeSort(vector<int>& v) {
    if (v.size() > 1) {
        vector<int> left(v.begin(), v.begin() + v.size() / 2);
        vector<int> right(v.begin() + v.size() / 2, v.end());

        mergeSort(left);
        mergeSort(right);

        int i1 = 0;
        int i2 = 0;

        for (int i = 0; i < v.size(); i++) {
            if (i2 >= right.size() || (i1 < left.size() && left[i1] < right[i2])) {
                v[i] = left[i1]; i1++;
            }
            else {
                v[i] = right[i2]; i2++;
            }
        }
    }
}

void printVector(vector<int>& v)
{
    for (auto i = v.begin(); i != v.end(); i++) cout << *i << ' ';
    std::cout << std::endl;
}

void test(vector<int>& v)
{
    std::cout << "------\n";
    printVector(v);
    mergeSort(v);
    std::cout << "------\n";
    printVector(v);
    std::cout << "------\n";
}

int main() {
    vector<int> v1 = { 22, 18, 12, -4, 58, 7, 31, 42 };
    vector<int> v2 = { 10 };
    vector<int> v3 = { 10 , 20 };
    vector<int> v4 = { 20 , 10 };
    vector<int> v5 = { 20 , 10 , 5};
    vector<int> v6 = { 10 , 10 , 10 };
    vector<int> v7 = { 11 , 10 , 10 };
    vector<int> v8 = { };
    test(v1);
    test(v2);
    test(v3);
    test(v4);
    test(v5);
    test(v6);
    test(v7);
    test(v8);
    return 0;
}

I'm somewhat new to coding, (or serious at coding if you will), I dont really know how to use a debugger properly, do you have any links that might be useful? It was a typo, I did i++ in the if case instead of i1++. and how did you decide to generate those test cases, just random, or did you have some insight on what might be a good test case? — Xgh05t, Dec 24 '19 at 14:52
You should accept an answer to close this issue. For debuggers, it depends on what you are using to write the code. Visual Studio if you are using Windows. gdb if you are in Linux. You should learn to debug your code quickly, it will be VERY useful later on. — fern17, Dec 24 '19 at 14:55
For tests cases, I tried to cover many cases that might happen. It is not perfect, though: you should test many more things (repeated values, negative and positive, even and odd number of values, big arrays... etc). — fern17, Dec 24 '19 at 14:59
I'm using VSCode, I'm not sure what those extra feature in Visual Studio are for, so I just went for lightweight option, it does have a debugger option though I'll look into it, thank you! — Xgh05t, Dec 24 '19 at 15:05

Trouble implementing Mergesort algorithm in c++, syntax of vectors

2 Answers2