C++ Mergesort Segmentation Fault?

Question

I seem to be having some trouble getting this mergesort to run. When I try to run it with g++ the terminal says "Segmentation fault (core dumped)," and I don't know what is causing this to happen (you might be able to tell that I'm still a beginner). Could anybody help out?

#include <iostream>
using namespace std;


void merge (int*, int, int, int);

void mergesort (int* A, int p, int r){

 if (p < r){

  int q = (p+r)/2;
  mergesort (A, p, q);
  mergesort (A, q+1, r);
  merge ( A, p , q, r);
  }
}

void merge (int* A, int p, int q, int r){


  int n = q-p+1;
  int m = r-q ;
   int L [n+1];
  int R [m+1];

  for (int i=1;i <n+1;i++)
       L[i] = A[p+i-1];

  for (int j=1; j< m+1; j++)
      R[j] = A[q+j];

L[n+1];
R[m+1];

 int i= 1;
 int j=1;

for (int k = p; k= r + 1; k++){
   if (L[i] <= R[j]){
      A[k] = L[i];
       i+=1;
   }
   else{
     j += 1;
    }
}
}


int main() {

int A [15] = {1, 5, 6, 7,3, 4,8,2,3,6};

mergesort (A, 0, 9);

for (int i=0; i <9; i++){
cout << A[i] << endl;
}

return 0;
}

Thanks a lot!

Answer 1

There are three things in your implementation that either don't make sense or are outright wrong:

First these:

L[n+1];
R[m+1];

Neither of these statement have any effect at all, and I've no idea what you're trying to do.

Next, a significant bug:

for (int k = p; k= r + 1; k++){

The conditional clause of this for-loop is the assignment k = r + 1. Since r does not change anywhere within your loop, the only way that expression is false is if r == -1, which it never is. You've just created an infinite-loop on a counter k that will run forever up into the stratosphere, and in the process index, and write, to memory no longer valid in your process. This, as a result, is undefined behavior. I'm fairly sure you wanted this:

for (int k = p; k< (r + 1); k++){

though I can't comment on whether that is a valid limit since I've not dissected your algorithm further. I've not take the time to debug this any further. that I leave to you.

Edit. in your main mergsesort, this is not "wrong" but very susceptible to overflow

int q = (p+r)/2;

Consider this instead:

int q = p + (r-p)/2;

And not least this:

int L [n+1];
int R [m+1];

Uses a variable-length array extension not supported by the standard for C++. You may want to use std::vector<int> L(n+1) etc.. instead.

Answer 2

In your case the segmentation fault is likely being caused when you are trying to read memory in that does not exist for a variable, for example say you have an array called foo of size 10 (so foo[10]) and you this statement foo[11] would cause a segmentation fault.

What you need to do is use debug statements to print out your index variables (i, j, n, m, p and q) and see if any of these are larger than your array sizes

EDIT: Another unrelated issue is that you should not use using namespace std, this line of code can cause scoping issues if you are not careful, just something to keep in mind :)