Segmentation fault while passing array as parameter in c

Question

As an assignment I have to implement mergesort. I am getting segmentation faults as I am passing array as an argument. Everything appears to be correct. I am attaching the code.
arr is int arr[1000], I am passing it to mergesort as
mergesort(arr, 0, n);

Remaining code is as follows.

void merge(int a[], int l, int m, int r)
{
    int temp[r -l];
    int templ = l;
    int tempm = m;
    register int k; 
    for(k=0; k<(r-l); k++)
    {
    if((tempm >= r)||(templ < m)&&(a[templ] <= a[tempm]))
    {   /*if number from left subarray is smaller*/
    temp[k] = a[templ];
    templ++;
    }
    else
    {   /*number from right subarray is smaller*/
    temp[k] = a[tempm];
    tempm++;
    }
    }
    for(k= l; k< r; k++)
    {   /*copy results back to the array to be returned*/
    a[k] = temp[k - l];
    }
}

void mergesort(int ar[], int left, int right)
{
    int mid;    
    if(left < right)
    {
    mid= (left + right)/2;
    mergesort(&ar[0], left, mid - 1);
    mergesort(&ar[0], mid, right);
    merge(&ar[0], left, mid, right);
    }
}

Everywhere you use &ar[0] you could use the equivalent and simpler ar instead. In this case, using the array name is the same as passing the address of element 0. — Blastfurnace
– Blastfurnace, Commented Mar 10, 2013 at 22:30

user2088639 · Accepted Answer · 2013-03-10 21:38:45Z

1

Once you have left == 0 and right == 1 in mergesort, you are going to have an infinite recursion:

void mergesort(int ar[], int left, int right) // IF LEFT IS 0 AND RIGHT IS 1 HERE...
{
    int mid;    
    if(left < right) // ...THEN LEFT IS LESS THAN RIGHT AND...
    {
    mid= (left + right)/2;
    mergesort(&ar[0], left, mid - 1);
    mergesort(&ar[0], mid, right); // ...HERE WE HAVE A CALL THAT IS
    // IDENTICAL TO THE ONE THAT GOT US HERE, INFINITE RECURSION

answered Mar 10, 2013 at 21:38

user2088639

Sign up to request clarification or add additional context in comments.

8 Comments

Shreyas Kale Over a year ago

@wilsonmichaelpatrik : but we are reducing right and increasing left as we are going on calculating mid in every call. so at one point, left might become greater than right. so it will stop the recursion. can you tell me briefly how you are thinking about it?

Alexander Atanasov Over a year ago

what happens when you call mergesort(&ar[0], 0, 1);

user2088639 Over a year ago

Assuming we're in mergesort with left as 0 and right as 1, then left < right is true, mid is (0 + 1) / 2 which is 0, then mergesort(&ar[0], left, mid - 1) is called and returns, then mergesort(&ar[0], mid, right) is called with mid as 0 and right as 1, which is identical to the call we're currently in. And when we're in that call, we'll again call mergesort(&ar[0], 0, 1) ad infinitum.

Shreyas Kale Over a year ago

it keeps up calling mergesort until left < right, and then it calls merge, as you can see it is below the mergesort call, which merges two arrays in sequence, and then it returns merged list as the recursive calls unwind (return).

user2088639 Over a year ago

It's never going to get to merge though. Every call to mergesort(&ar[0], 0, 1) results in another call to mergesort(&ar[0], 0, 1) before merge(&ar[0], left, mid, right) is ever reached. It's simple enough to test, just call mergesort(&ar[0], 0, 1) directly in a debugger and see what happens.

|

Collectives™ on Stack Overflow

Segmentation fault while passing array as parameter in c

1 Answer 1

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related