Problem with Mergesort in C++

Question

vector<int>& mergesort(vector<int> &a) {
    if (a.size() == 1) return a;
    int middle = a.size() / 2;
    vector<int>::const_iterator first = a.begin();
    vector<int>::const_iterator mid = a.begin() + (middle - 1);
    vector<int>::const_iterator last = a.end();
    vector<int> ll(first, mid);
    vector<int> rr(mid, last);

    vector<int> l = mergesort(ll);
    vector<int> r = mergesort(rr);
    vector<int> result;
    result.reserve(a.size());
    int dp = 0, lp = 0, rp = 0;

    while (dp < a.size()) {
        if (lp == l.size()) {
            result[dp] = (r[rp]);
            rp++;
        } else if (rp == r.size()) {
            result[dp] = (l[lp]);
            lp++;
        } else if (l[lp] < r[rp]) {
            result[dp] = (l[lp]);
            lp++;
        } else {
            result[dp] = (r[rp]);
            rp++;
        }
        dp++;
    }
    a = result;
    return a;
}

It compiles correctly but while execution, I am getting:

This application has requested the runtime to end it in an unusual way.

This is a weird error.

Is there something that is fundamentally wrong with the code?

Answer 1

This result.reserve(a.size()) just affects the vector's capacity, not it's size. (The vector's capacity tells up to which size the vector can grow without needing to re-allocate and copy all members. Basically it's only there for optimization purposes.) You cannot access any members in result after that reservation, since there aren't any. Either use result.push_back(...) instead of result[dp] = ... or result.resize(a.size()) instead of result.reserve(a.size()).

I suppose the former could be more effective.

Answer 2

reserve() does not change the amount of contents in the vector. You've created an empty vector, reserved a certain size for it, and then used v[i] = x; This is not a valid use of vector since there still isn't any i'th element in the vector.

Use resize() instead.

Answer 3

One problem is with the usage of reserve() (either use resize() or append items with push_back() instead of accessing the index).

---

if (a.size() == 1) return a;
int middle = a.size() / 2;
vector<int>::const_iterator first = a.begin();
vector<int>::const_iterator mid = a.begin() + (middle - 1);
vector<int>::const_iterator last = a.end();
vector<int> ll(first, mid);
vector<int> rr(mid, last);

This could be another problem. If the size is 2, then ll would end up being an empty vector, and this function doesn't appear to handle this. There doesn't seem to be much reason to subtract 1 from middle anyway.

---

It is also possible that you are copying things around far more than needed: you shouldn't need the l and r vectors (because they will just be copies of ll and rr), similarly I don't think you need the result vector, since you could just write the merged results right back to a.

Answer 4

The error message is very unclear, because it is the standard message of VC++ when an exception goes unhandled. You could add a try-catch-clock to your main to get the exception and a more meaningful error:

int main() {
    try {
        // do main stuff here
    }
    catch ( std::exception & e ) {
        std::cout << e.what() << std::endl;
    }
}

This is for the command-line. If your application doesn't have one, use a message box or write the error to a log-file.

With regard to the problem in your code, all the other answers appear to be correct.