C中合并排序中的分段错误

Question

我最近尝试实现合并排序算法。我理解它背后的基本概念，甚至在网上看了一眼它的一个C实现，但当我试图自己做时，我似乎总是会遇到分段错误。我也很困惑是在某些地方使用mid还是mid+1。

请帮我解决这个问题。

#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;
}

Answer 1

访问未分配的内存时会出现分段故障。在mergeSort函数中，通过将索引传递给merge函数来调用merge函数。

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

在merge函数内部，当您声明leftSide和rightSide数组时，数组的大小应该是index+1，因为数组索引从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.

Answer 2

在for(int m,l,r=0; m<=high; m++)中，变量m和l未初始化。您只将r设置为0。这意味着您可能会使用非法索引对arr[]和leftSide[]进行索引，从而导致segfault。

变量m、l、r被称为自动变量，它们是默认的未初始化变量。

此外，在leftSide[]和rightSide[]之间拆分arr[]时，将arr[mid]值放置到两个数组中。