CODEWITHSUNDEEP
c
Andy
Andy

Reputation: 950

Segmentation Fault with Merge Sort

I've recently begun brushing up on my C again after having not touched it for some time. So, I started by trying to implement merge sort but after looking at these lines for about an hour, I've failed to determine what is wrong.

int main(int argc,char** argv){
    printf("test\n");
    int x;
    int input[] = {1,2,3};
        int start=0;
        int end=2;
    for (x=0;x<5;x++){
        //printf("%i\n",x);
    }
    printf("Run mergeSort in main \n");
    mergeSort(input,start,end);

}

void mergeSort(int input[], int start, int end){
    printf("Running merge %i %i",start,end);
    int middle = (start + end)/2;
    if (start < end){
        mergeSort(input,start,middle);
        mergeSort(input,middle+1,end);
        merge(input,start,middle,end);
    }
}

When I run this program, the first line "test" will print then "Run merge sort in main" but

printf("Running merge %i %i",start,end);

does not get executed which leaves me confused. I can't find any memory allocation issues or maybe I'm missing something very obvious.

Note that the merge function has been implemented on the side, but that portion of the code was not relevant to this problem directly so I did not include it.

EDIT Remaining Code:

void merge(int input[],int start, int middle, int end){
    int save_start = start;
    int temp[end-start+1];
    int index = 0;
    printf("Start merge");
    while (start<=middle || middle+1<=end){
        if (input[start]<input[middle]){
            temp[index] = input[start];
            start++;
        } else {
            temp[index] = input[middle];
            middle++;
        } 
        index++;
    }
    while  (start<=middle){
        temp[index] = input[start];
        start++;
    }

    while (middle+1<=end){
        temp[index] = input[middle];
        middle++;
    }

    int i=0;
    int a;
    for (a=save_start;i<index;a++,i++){
        input[a]=temp[i];
    }

}

Upvotes: 0

Views: 497

Answers (2)

autistic
autistic

Reputation: 15632

I believe your mistake is here: while (start<=middle || middle+1<=end).

start<=middle || middle+1<=end is true when one or more of these is true: start<=middle or middle+1<=end, causing your code to read and write out of bounds of your arrays in that loop.

start<=middle && middle+1<=end is true when all of these are true: start<=middle and middle+1<=end, causing your loop to break when it might otherwise read and write out of bounds of your array.

You probably mean while (start<=middle && middle+1<=end).

Upvotes: 1

Carl Norum
Carl Norum

Reputation: 224844

Most likely your output is buffered and is just waiting around to get printed. Add a \n to that string or call fflush(stdout).

As far as your segmentation fault is concerned, you haven't shown us enough code. Use a debugger to get a backtrace and you may find out some more information.

Edit: You have some array index bugs in your merge function. Notice that you're moving middle during the first loop there - what does that do to the loop condition? Hint: you need to stop at the actual middle position, not keep going once start gets past that point.

Edit 2: You have some off-by-one errors in there too.

Edit 3: Your || should be &&.

Upvotes: 1

Related Questions