C中的递归合并排序与内存分配

Question

为了在C中设置一个合并排序递归函数，我想出了以下内容。

奇怪的行为是，当数组的大小很小(约为10)时，它工作得非常好。对于大小从10到15的值，它有时不正确地排序(一个或两个值被随机放置在最后的数组中)，而对于大于15的值，它总是对一个或两个值进行错误的排序，并用一个非常大的负数替换一个或两个整数值。

例如，这个数组：[3] [9] [2] [11] [8] [7] [5] [2]

得到这样的排序：[2] [2] [3] [-254587859] [7] [8] [11]

--

下面是我想出的代码：

main() :

int main(int ac, char **av)
{
    int size = atoi(av[1]);
    int *array = malloc(size*sizeof(int));
    int i;

    for (i = 0; i < size; i++) { array[i] = rand() % size; }

    merge_sort(array, 0, size-1);

    print_array(array, size);

    free(array);

    return 0;

}

merge_sort() :

void merge_sort(int array[], int beg, int end)
{
    int mid = (end + beg) / 2;

    if (beg < end)
    {
        merge_sort(array, beg, mid);
        merge_sort(array, mid+1, end);
        merge(array, beg, mid, end);
    }

    return;
}

merge() :

void merge(int array[], int beg, int mid, int end)
{
    int size_left = mid - beg + 1;
    int size_right = end - mid;
    int *left = malloc((size_left)*sizeof(int));
    int *right = malloc((size_right)*sizeof(int));
    int i,j,k;

    for (i = 0; i < size_left; i++) { left[i] = array[beg+i]; }
    for (j = 0; j < size_right; j++) { right[j] = array[mid+1+j]; }

    i = 0; j = 0; for (k = beg; k <= end; k++) { array[k] = (left[i] <= right[j]) ? left[i++] : right[j++]; }

    free(left); free(right);

    return;
}

我想这是一个内存分配问题，我可以分配大量的内存(我试过了，而且可以工作)，但这不是重点。你知道那里发生了什么事吗？

配置: gcc 4.6.2，Windows 7 64位。

Answer 1

我猜问题出在线上：

for (int k = beg; k <= end; k++) {
    array[k] = (left[i] <= right[j]) ? left[i++] : right[j++];
}

比如left = [1, 2, 3, 4]和right = [5, 6, 7, 8]。左边将被取为i = 4，然后尝试引用数组之外的left[4]，它具有未定的值(在Java或其他安全语言中，您将得到IndexOutOfBoundException或类似的错误--在C中，您是自己的，您刚刚读取了一些随机内存)。

您需要确保i和j在数组范围内。例如：

 for (int k = beg; k <= end; k++) {
    if (i == size_left) {
        array[k] = right[j++];
    } else if (j == size_right) {
        array[k] = left[i++];
    } else {
        array[k] = (left[i] <= right[j]) ? left[i++] : right[j++];
    }
}

不幸的是，这种错误在C中很常见。有一些工具，包括免费的和商业的，可以让您找到它们。对于Linux，通常使用瓦兰。CLang或gcc 4.8.0+ AddressSanitizer也会帮助解决这个问题--不幸的是，除了它，我不知道其他任何免费的Windows工具。

Answer 2

问题在于您的合并：

array[k] = (left[i] <= right[j]) ? left[i++] : right[j++];

这并不能解释i或j可能超过数组结束的事实。你需要实际检查：

i = j = 0;
k = beg;

// Merge both
while( i < size_left && j < size_right ) {
    array[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
}

// Merge leftovers
while( i < size_left ) array[k++] = left[i++];
while( j < size_right ) array[k++] = left[j++];

Answer 3

好吧，谢谢你，麦琪和帕迪，在我关于“合并”步骤的推理中，你指出了一个很大的失败。这正是C带来的有趣之处，即你“独自一人”，如果你走错了一步，就没有什么准则能阻止你。

基于您的改进，下面是我最后的结论：

for (k = beg; k <= end; k++) {
    array[k] = (left[i] <= right[j]) ?
        (i == size_left) ? right[j++] : left[i++] :
        (j == size_right) ? left[i++] : right[j++];
}