Segmentation Fault in Merge Sort in C-CodePudding

I recently tried to implement the merge sort algorithm. I understood the basic concept behind it and even took a peek at one of it's C implementations online but when I try to do it on my own, I always seem to get a segmentation fault. I am also confused if to use mid or mid 1 in places.

Please help me fix this.

#include <stdio.h>
#include <math.h>
int merge(int arr[], int low, int mid, int high);
int mergeSort(int arr[], int low, int high);
int main(void)
{
    int sample[5]={66,7,11,2,99}; //Sample array for sorting.
    mergeSort(sample, 0, 4); //Calling the function
    
}
int merge(int arr[], int low, int mid, int high)
{
    if(high>low) //Merge will only work when high is greater than low and mid.
    {
        int leftSide[mid]; // Dividing the array into two parts, this is the left side; low to mid.
        int rightSide[(high-mid)];  //This is the right side; mid to high.
        for(int i=0;i<=mid;i  )
        {
            leftSide[i]=arr[i]; //Filling the leftSide array.
        }
        for (int x=mid; x<=high; x  )
        {
            rightSide[x]=arr[x]; //Filling the rightSide array.
        }
        for(int m,l,r=0; m<=high; m  )
        {
            if(leftSide[l]>rightSide[r])
            {
                arr[m]=rightSide[r]; //If the element on rightSide is lesser than on the leftSide then it will come first in the final array.
                r  ; //Increment the counter so next comparision can begin.
            }
            else if(leftSide[l]<rightSide[r])
            {
                arr[m]=leftSide[l]; //If the element on leftSide is lesser than on the rightSide then it will come first in the final array
                l  ; //Increment the counter so next comparision can begin.
            }
            else //This will be the case if the numbers are equal
            {
                if(l<mid) //If the left Index has not reached its maximum limit 
                {
                    arr[m]=leftSide[l]; 
                    l  ;
                }
                else if(r<(high-mid)) // If the right Index has not reached its maximum limit
                {
                    arr[m]=rightSide[r];
                    r  ;
                }
            }
        }
        return 0;
    }
    else
    {
        return 1;
    }
}

int mergeSort(int arr[], int low, int high)
{
    if(high>low)
    {
        int mid=round((high low)/2);
        mergeSort(arr, low, mid);
        mergeSort(arr, mid, high);
        merge(arr, low, mid, high);

    }
    else //Base Case
    {
        return 1;
    }
    for(int i=0; i<=high;i  ) //Printing the array.
    {
        printf("%d",arr[i]);
    }
    return 1;
}

CodePudding user response：

Segmentation fault occur when you access unallocated memory. In mergeSort function, you called merge function by passing indexes to call merge function.

    if(high>low)
    {
        int mid=round((high low)/2);
        mergeSort(arr, low, mid);
        mergeSort(arr, mid, high);
        merge(arr, low, mid, high);

    }

Inside merge function when you declared leftSide and rightSide arrays, The size of arrays should be index 1, As array index starts from 0.

        int leftSide[mid   1]; // Dividing the array into two parts, this is the left side; low to mid.
        int rightSide[(high-mid)   1];  //This is the right side; mid to high.

CodePudding user response：

In for(int m,l,r=0; m<=high; m ) the variables m and l are uninitialized. You only set r to 0. This means you will potentially index into arr[] and leftSide[] with illegal indices, causing a segfault.

The variables m, l, r are so called automatic variables, and these are default uninitialized.

Also, when you split arr[] between leftSide[] and rightSide[], you are placing the arr[mid] value into both arrays.