Merge Sort Segmentation fault

[hasslersteph]

I have been trying to identify the bug in this code for a long time to no avail. It is a merge sort code I tried writing myself. I am getting a Segmentation fault everytime I try to run the code. It runs on smaller cases well.

Thank you for your help!

  // Main function of the C++ program.

#include <iostream>
using namespace std;
void printarray(int a[],int size);
void splitsort(int b[], int start, int end); //Split array into half
void merge(int b[], int start, int end); // merge the sorted arrays



int main()
{
    cout<<"This is merge sort"<<endl;
    int array[]={9,8,7,6,5,4,3,2,1};
    int length=sizeof(array) / sizeof(array[0]);
    printarray(array,length);
    splitsort(array,0,length-1);
    cout<<"sorted array"<<endl;
    printarray(array,length);
    return 0;
}

void printarray(int a[],int size){
    for(int i=0;i<size;i++){
        cout<<a[i]<<",";
    }
    cout<<endl;
    return;
}


void splitsort(int b[], int start, int end){
    //base case
    if(end==start){return;}

    //
    splitsort(b,start,(start+end)/2);
    splitsort(b,(start+end)/2+1,end);
    merge(b,start,end);

    return;
}


void merge(int b[], int start, int end){
    int tempb[(end-start)+1];

    //base case
    if (end==start){return;} // if single element being merged
    int i=start;
    int j=(start+end)/2+1;
    for(int k=start;k<=end;k++){
        if(i==(start+end)/2+1){tempb[k]=b[j];j++;}// finished first array
        else if(j==end+1){tempb[k]=b[i];i++;}// finished second array
        else if (b[i]>=b[j]){
            tempb[k]=b[j];
            j++;
        }
        else if(b[j]>=b[i]) {
            tempb[k]=b[i];
            i++;
        }
    }

    for(int k=start;k<=end;k++){
        b[k]=tempb[k];
    }

    return;

}

[Thomas1965]

Your code works on the shell.
What compiler / IDE do you use?

[tryinghard]

In your void splitsort function, the terminating condition is not true.
It should return back when (end>start).

if(end>start)
return;
This will remove the Segmentation Fault. Also the code is incorrect. Figure out your mistake.

[lastchance]

Your array tempb[] is not big enough. Because you are using the indices of the whole of b[], it needs to be the same size as the whole of b[], and not just the bit between start and end.

In other words, if you intend to index like this (and you don't have to) then, on line 46, array tempb[] needs to have size end+1 and not (end-start)+1. For example, at one stage of the merge sort you will have start=7, end=8 and you will declare a temporary array of length 2 ... but you will be addressing its index 8.

Line 46 is actually illegal in strict standard C++ (although allowed in the C99 version of C): it's a variable-length array (VLA); turn your compiler warnings up. You can create a dynamic array of the right size by
int *tempb = new int[1+end];
but remember to
delete [] tempb;
before returning.


Other than this, your indexing makes your code easy to follow. However, if you wanted to reduce the size of memory in temporary arrays then you could send splitsort and merge pointers to b[start] and just pass the reduced size of array (end-start+1) as a size.

Thomas1965 wrote:

Your code works on the shell.

No it doesn't. Surprisingly, it doesn't seem to crash, but it doesn't sort anything either. The original array (which is reverse-ordered) is printed, but not the sorted array.

tryinghard wrote:

In your void splitsort function, the terminating condition is not true.
It should return back when (end>start).

That is nonsense.

tryinghard wrote:

if(end>start)
return;
This will remove the Segmentation Fault.

Obviously; but it won't sort anything either.

tryinghard wrote:

Also the code is incorrect. Figure out your mistake.

That's not very helpful.

[hasslersteph]

Thanks a lot for your suggestions. Fixing the temporary array size makes the code run well without any errors.