Stackoverflow in recursion. How can I fix it?

[joseplusplus]

Hello there !

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 = new int[n1 + 1];
  int *right = new int[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;
    } else if(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..

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

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.

Best Regards,

J.

[ne555]

Debugger, backtrace.


¿why do you return things that you are never going to use?

[joseplusplus]

Hello,

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,

Thanks for your reply, sir,

Sincerely

[cire]

Could you please explain to me, where is it that I'm returning things that I'm not using?

Two things are obvious. mergesort is supposed to return a value. It does not.

merge returns a value, but it is always discarded.