What is wrong with my merge sort?

Question

I wanted to write a merge sort using pointers, but when I tried doing it in C, I got a segmentation fault. I expected a segmentation fault, but not where i actually got it. Here's my code:

#include <stdio.h>
#include <stdlib.h>


int *merge(int [], int *, int *, int *); 
int *mergesort(int [], int *, int *); 

int main(){
    int n[] = {4, 2, 9, 5, 10, 11, 1, 0}; 
    int *m = mergesort(n, n, n + 7); 

    int i;
    for(i = 0; i < 7; i++)
        printf("[%d]\n", n[i]); 

    return 0;

}

int *mergesort(int *a, int *p, int *r){
    if(p >= r)
        return a; 

    int *q = p + (q - p)/2;
    mergesort(a, p, q); 
    mergesort(a, q+1, r); 

    return merge(a, p, q, r);   
}
/*0, 1, 2, 3, 4, 5, 6, 7*/
int *merge(int *a, int *p, int *q, int *r){
    /*int *arrone = new int[q - p + 1]; 
    int *arrtwo = new int[r - q]; */

    int *arrone = malloc(sizeof(int) * (q - p + 1));
    int *arrtwo = malloc(sizeof(int) * (r - q)); 

    int i;
    for(i = 0; p + i <= q; i++)
        arrone[i] = p[i]; 

    for(i = 0; q + i + 1 <= r; i++)
        arrtwo[i] = *(q + 1 + i); 

    int j;
    for(j = 0; arrone <= q && arrtwo <= r; j++){
        if(*arrone < *arrtwo)
            a[j] = *arrone, arrone++; 
        else
            a[j] = *arrtwo, arrtwo++; 
    }

    if(arrone <= q)
        for(; p + j <= r; j++)
            a[j] = *arrone++; 
    else
        for(; p + j <= r; j++)
            a[j] = *arrtwo++;

    free(arrone);
    free(arrtwo);

    return a; 
}

Now the weird part is that I get this segmentation fault right at the first call to mergesort. In DDD, the second it touches this function it errors out. DDD gives me this

Program received signal SIGSEGV, Segmentation fault. (Very long address) in mergesort (a<= error reading variable: Cannot access memory at address 0x7fffff7feff8, p=< error reading variable: Cannot access memory at 0x7fffff7feff0, r=< error reading variable: cannot access memory at address 0x7fffff7fefe8) at (line where mergesort begins its definition)

When I backtrace it however, it supplies an infinite amount of calls at the lines where the second mergesort is called in merge, though I can't see why that'd be any different from where the first one is called (actually that one is also highlighted in frame 0 of my gdb backtrace)

What did I do wrong this time?

Answer 1

What is q here? you are declaring *q and initializing using q in expression..

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

Also,

a[j] = *arrtwo++;   <-- Here increment of pointer is happening instead of value

should be used as

a[j] = (*arrtwo)++;

and hence subsequently failing in free(..). Check all such instances.

I think your pointer increment logic can be correct, but you can not free updated pointer which may be pointing to something else all together.

Answer 2

Problem is here ----- int *q = p + (q - p)/2;

You are assigning value to *q before initialising q So q has garbage value and above statement will assign garbage value to *q.

What logic is in your mind for --- int *q = p + (q - p)/2;