递归函数分段失败

Question

我将编写4路合并排序，但我将分段失败作为一个错误。

我觉得这与递归深度无关，因为它为我的测试用例递归调用了20次。

当我删除mergesort_4_way_rec中的merge_4_way时，它可以顺利运行。我可以找出导致错误的merge_4_way的任何函数设计问题。我使用clang进行编译，使用MacOS进行测试。

#include <stdio.h>
#include "merge_sort.h"
// merge the four sub-array
// [low, mid1), [mid1, mid2), [mid2, mid3), [mid3, high)
void merge_4_way(int* array, int low, int mid1, int mid2, int mid3, int high) {
int i = low, j = mid1, k = mid2, p = mid3, l = low;
int destArray[high - low];

while((i < mid1) && (j < mid2) && (k < mid3) && (p < high))  
{  
if( (array[i] <= array[j]) && (array[i] <= array[k]) && (array[i] <= array[p])) 
{
destArray[l++] = array[i++]; 
}
else if ((array[j] <= array[i]) && (array[j] <= array[k]) && (array[j] <= array[p]))
{
destArray[l++] = array[j++]; 
}
else if ((array[k] <= array[i]) && (array[k] <= array[j]) && (array[k] <= array[p]))
{
destArray[l++] = array[k++];
}
else if ((array[p] <= array[i]) && (array[p] <= array[j]) && (array[p] <= array[k]))
{
destArray[l++] = array[p++];
}
}

// case where first and second ranges 
// have remaining values  
while ((i < mid1) && (j < mid2) && (k < mid3))  
{  
if((array[i] <= array[j]) && (array[i] <= array[k])) 
{ 
destArray[l++] = array[i++]; 
} 
else if ((array[j] <= array[i]) && (array[j] <= array[k])) 
{ 
destArray[l++] = array[j++]; 
}
else if ((array[k] <= array[i]) && (array[k] <= array[j])) 
{ 
destArray[l++] = array[k++]; 
}  
} 

// case where first and second ranges 
// have remaining values  
while ((i < mid1) && (j < mid2) && (p < high))  
{  
if((array[i] <= array[j]) && (array[i] <= array[p])) 
{ 
destArray[l++] = array[i++]; 
} 
else if ((array[j] <= array[i]) && (array[j] <= array[p])) 
{ 
destArray[l++] = array[j++]; 
}
else if ((array[p] <= array[i]) && (array[p] <= array[j])) 
{ 
destArray[l++] = array[p++]; 
}  
}
while ((i < mid1) && (k < mid3) && (p < high))  
{  
if((array[i] <= array[k]) && (array[i] <= array[p])) 
{ 
destArray[l++] = array[i++]; 
} 
else if ((array[k] <= array[i]) && (array[k] <= array[p])) 
{ 
destArray[l++] = array[k++]; 
}
else if ((array[p] <= array[i]) && (array[p] <= array[k])) 
{ 
destArray[l++] = array[p++]; 
}  
} 
while ((j < mid2) && (k < mid3) && (p < high))  
{  
if((array[j] <= array[k]) && (array[j] <= array[p])) 
{ 
destArray[l++] = array[j++]; 
} 
else if ((array[k] <= array[i]) && (array[k] <= array[p])) 
{ 
destArray[l++] = array[k++]; 
}
else if ((array[p] <= array[j]) && (array[p] <= array[k])) 
{ 
destArray[l++] = array[p++]; 
}  
}
// case where first and second ranges 
// have remaining values  
while ((i < mid1) && (j < mid2))  
{  
if(array[i] <= array[j]) 
{ 
destArray[l++] = array[i++]; 
} 
else
{ 
destArray[l++] = array[j++]; 
} 
}  

// case where second and third ranges 
// have remaining values  
while ((j < mid2) && (k < high))  
{  
if(array[j] <= array[k]) 
{ 
destArray[l++] = array[j++]; 
} 
else
{ 
destArray[l++] = array[k++]; 
}  
}    
// case where third and forth ranges 
// have remaining values  
while ((k < mid3) && (p < high))  
{  
if(array[k] <= array[p]) 
{ 
destArray[l++] = array[k++]; 
} 
else
{ 
destArray[l++] = array[p++]; 
}  
}  

// case where first and third ranges have  
// remaining values  
while ((i < mid1) && (k < mid3))  
{  
if(array[i] <= array[k]) 
{ 
destArray[l++] = array[i++]; 
} 
else
{ 
destArray[l++] = array[k++]; 
}  
}
// case where first and forth ranges have  
// remaining values  
while ((i < mid1) && (p < high))  
{  
if(array[i] <= array[p]) 
{ 
destArray[l++] = array[i++]; 
} 
else
{ 
destArray[l++] = array[p++]; 
}  
} 
// case where second and forth ranges have  
// remaining values  
while ((j < mid2) && (p < high))  
{  
if(array[j] <= array[p]) 
{ 
destArray[l++] = array[j++]; 
} 
else
{ 
destArray[l++] = array[p++]; 
}  
}
// copy remaining values from the first range  
while (i < mid1)  
destArray[l++] = array[i++];  

// copy remaining values from the second range  
while (j < mid2)  
destArray[l++] = array[j++];  

// copy remaining values from the third range  
while (k < mid3)  
destArray[l++] = array[k++];

// copy remaining values from the third range  
while (p < high)  
destArray[l++] = array[p++];
for (int i = low; i < high; i++){
array[i] = destArray[i];
} 

}
// divide the array [low, high) into 4 parts (roughly same size).
// For each part, if # of items > 3, recursively call mergesort_4_way_rec; 
// Otherwise sort them as you like
// Finally use merge_4_way merge them
void mergesort_4_way_rec(int* array, int low, int high) {
int mid1 = low + ((high-low) / 4);
int mid2 = low + 2 * ((high-low) / 4);
int mid3 = low + 3 * ((high-low) / 4);
printf("%dn", (high - low));
if ((high - low) > 3){
mergesort_4_way_rec(array, low, mid1);
mergesort_4_way_rec(array, mid1, mid2);
mergesort_4_way_rec(array, mid2, mid3);
mergesort_4_way_rec(array, mid3, high);
merge_4_way(array, low, mid1, mid2, mid3, high);
} else {
for(int i=low; i<high;i++)
{
for(int j=low;j<high-i-1;j++)
{
if(array[j]<array[j+1])
{
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
} 
return;  
}


}

Answer 1

如果low不是0，那么您将在destArray结束后进行写入。

destArray的大小为high - low。将l(写入destArray时使用的索引变量(初始化为low，因此最终写入元素destArray[low]到destArray[high - 1]，如果low不为零，则该元素将超过末尾。

一种解决方案是初始化l = 0;，并将merge_4_way末尾的循环更改为适当地索引destArray。

另一种解决方案是用int destArray[high];声明destArray为所有元素都有空间，即使是未使用的元素，尽管这会浪费堆栈空间。