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....
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;
}