sortingdebuggingmemorymergesort

Why in this mergesort do I get problems with memory?


I've tried to write function for mergesort, but when I try to debug it I get whether 'stack overflow' or 'violation of access rights when writing to the address'. What might be the problem???

void Merge(vector<int>a, int l, int m, int r) {
    int i = l, j = m, k = 0;
    vector<int> b(a.size());
    while (i < m && j < r) {
        if (a[i] < a[j])
            b[k] = a[i];
            i++
        else 
            b[k] = a[j];
            j++;
        k++;
    }
    while (i < m) {
        b[k] = a[i];
        k++;
        i++;
    }
    while (j < r) {
        b[k] = a[j];
        k++;
        j++;
    }
    for (int x = 0; x < a.size(); x++)
        a[x] = b[x];
    delete &b;
}

void Mergesort(vector<int>& a, int l, int r) {
    if (l >= r)
        return;
    int mid = l + (r - l) / 2;
    Mergesort(a, l, mid);
    Mergesort(a, mid, r);
    Merge(a, l, mid, r);
}

int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    Mergesort(a, 0, n-1);

    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
}

I can't get what is wrong here....


Solution

  • stack overflow occurs when l = 0 and r = 1, will get stuck on mid = 0, r = 1 and recurse until stack overflow. I changed code so that r is the end index (last index + 1).

    Fixes noted in comments:

    #include <iostream>
    #include <vector>
    
    void Merge(std::vector<int>&a, int l, int m, int r) {   // fix &a
        int i = l, j = m, k = l;            // fix k = l
        std::vector<int> b(a.size());
        while (i < m && j < r) {
            if (a[i] <= a[j]) {             // fix {
                b[k] = a[i];
                i++;
            } else {                        // fix } {
                b[k] = a[j];
                j++;
            }                               // fix }
            k++;
        }
        while (i < m) {
            b[k] = a[i];
            k++;
            i++;
        }
        while (j < r) {
            b[k] = a[j];
            k++;
            j++;
        }
        for (k = l; k < r; k++)                // fix copy back l to r
            a[k] = b[k];
        //                                        fix b is local, don't delete
    }
    
    void Mergesort(std::vector<int>& a, int l, int r) {
        if ((r-l) < 2)                      // r is end instead of last
            return;
        int mid = l + (r - l) / 2;
        Mergesort(a, l, mid);
        Mergesort(a, mid, r);
        Merge(a, l, mid, r);
    }
    
    int Rnd32()
    {
    static uint32_t r = 0;
        r = r*1664525 + 1013904223;
        return (int)r;
    }
    
    #define n (1024)
    
    int main() {
        std::vector<int> a(n);
        int i;
        for (i = 0; i < n; i++)
            a[i] = Rnd32();
    
        Mergesort(a, 0, n);                 // fix n is end instead of last
    
        for (i = 1; i < n; i++){
            if(a[i-1] > a[i])
                break;
        }
        if(i == n)
            std::cout << "passed" << std::endl;
        else
            std::cout << "failed" << std::endl;
    
        return 0;
    }