c - C中的合并排序错误

Question

我想实现归并排序，即使我正在上的类(class)不需要它。

下面是我的代码，我留下了一些 printf 函数来演示错误。

该程序似乎可以工作，但是当我在递归中进行最后的几次合并时，它开始超出数组的参数并开始比较垃圾值。它起作用是因为这些值是正数，但如果一个是负数，它会将值存储在我的数组中。

我已尝试找到该错误，但我认为它与关系运算符有关，但我找不到修复方法。

任何指向正确方向的观点都将不胜感激。

#include <stdio.h>

#define SIZE 21

int temp_array[SIZE] = {0};

void sort(int array[], int start, int end);
void merge(int array[], int start_1, int end_1, int start_2, int end_2);

int main()
{

    int array[SIZE] = {10, 1, 8, 3, 6, 5, 4, 7, 2, 9, 0, 100, 91, 98, 93, 96, 95, 94, 97, 92, 99};

    sort(array, 0, SIZE-1);

    for(int i = 0; i < SIZE; i++)
    {
        printf(" %i ", array[i]);
    }

}


void sort(int array[], int start, int end)
{
    if (end > start)
    {
        int middle = (start + end) / 2;

        // sort left half
        printf("sorting left half\n");
        sort(array, start, middle);

        // sort right half
        printf("sorting right half\n");
        sort(array, middle + 1, end);

        // merge the two halves
        printf("####MERGING#####\n");
        merge(array, start, middle, middle + 1, end);

    }
}

void merge(int array[], int start_1, int end_1, int start_2, int end_2)
{
    int counter = 0;
    int s1 = start_1;

    while(start_1<=end_1 && start_2<=end_2)
    {
        printf(" %i %i and %i %i\n", start_1, end_1, start_2, end_2);

        if(array[start_1] < array[start_2])
        {
            printf("selecting %i over %i\n", array[start_1], array[start_2]);
            temp_array[counter++] = array[start_1++];
        }

        else
        {
            temp_array[counter++] = array[start_2++];
            printf("selecting %i over %i\n", array[start_2], array[start_1]);
        }
    }

    while (start_1 <= end_1)
    {
        temp_array[counter++] = array[start_1++];
        printf("Dumping Left Half: placing %i in position %i\n", array[start_1], counter);
    }

    while (start_2 <= end_2)
    {
        temp_array[counter++] = array[start_2++];
        printf(" Dumping Right Half: placing %i in position %i\n", array[start_2], counter);
    }

    for(int i = s1, j = 0; i <= end_2; j++, i++)
    {   
        printf("Placing %i in position %i\n", temp_array[j], i);
        array[i] = temp_array[j];
    }

    return;
}

Answer 1

在我看来可疑的一件事是在你的合并代码中的 else 里面:

temp_array[counter++] = array[start_2++];
printf("selecting %i over %i\n", array[start_2 /* HERE */], array[start_1]);

假设 start_2 == end_2 在上述执行之前成立，那么 printf 将从索引 end_2 + 1 读取，这将是sort 的最外层递归调用越界，因此出现未定义的行为(可能导致打印垃圾)。