I'm following an algorithms course, and as you know, a primordial algorithm is Merge-Sort; I tried to implement it following the famous CLRS book pseudo code; The Merge Step, I've managed to get to work quite well...
int* merge(int* array, int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
int *left = newint[n1 + 1];
int *right = newint[n2 + 1];
for(int i = 0; i < n1; ++i)
left[i] = array[p + i - 1];
for(int j = 0; j < n2; ++j)
right[j] = array[q + j];
left[n1] = 1000000; //sentinel
right[n2] = 1000000; //sentinel
int i = 0, j = 0;
for(int k = 0; k < r; ++k) {
if(left[i] <= right[j]) {
array[k] = left[i];
++i;
} elseif(right[j] < left[i]) {
array[k] = right[j];
++j;
}
}
delete [] left;
delete [] right;
return array;
}
But the MergeSort itself, the one that uses recursion heavily and calls the Merge-Step at the End, is a different Story; I don't know why it doesn't work..
1 2 3 4 5 6 7 8
int* mergesort(int* array, int p, int r) {
if(p < r) {
int q = (p + r) / 2;
mergesort(array, p, q - 1);
mergesort(array, q, r);
merge(array, p, q, r);
}
}
As it is, it's giving me a: "Segmentation fault: 11" error, when I call it like this...
1 2 3 4 5 6
int main() {
int array[] = { 2, 4, 5, 7, 1, 2, 3, 6 };
int size = sizeof(array)/sizeof(int);
int *merged = mergesort(array, 0, size);
return 0;
}
Can you please help me out, I really have NO Idea what's wrong. I've spent several hours trying to fix it with my limited knowledge.
Could you please explain to me, where is it that I'm returning things that I'm not using? I'm really clueless about the problem, so.. any further explanations would be really helpful,