C语言中的合并排序实现

Question

我正在学习如何在c中实现Mergesort，遇到了以下问题。

这是我的合并函数，它将两个排序数组合并为一个排序数组。

void merge(int *list, int *final, int start, int mid, int stop) {
    int h = start;
    int i = start;
    int j = mid + 1;

    while ((h <= mid) && (j <= stop)) {
        if (list[h] <= list[j]) {
            final[i] = list[h];
            h++;
        } else {
            final[i] = list[j];
            j++;
        }
        i++;
    }

    /* CODE A */
    if (h > mid) {
        for (int k = j; k <= stop; k++) {
            final[i] = list[k];
            i++;
        }
    } else {
        for (int k = h; k <= mid; k++) {
            final[i] = list[k];
            i++;
        }
    }
    /* End of CODE A */

    /* CODE B */
    while ( h <= mid) {
        list[i] = final[h];
        i++; h++;
    }

    while ( j <= stop ) {
        list[i] = final[j];
        i++; j++;
    }
    /* End of CODE B */

    for (int k = start; k <= stop; k++) {
        list[k] = final[k];
        printArray(list, 4, "Intermediate Array: ");
    }
}

在任何时候，我都使用代码A或代码B。当我使用代码A时，函数按预期执行。然而，当我使用CODE B时，函数会用随机数据填充数组列表。

printArray是一个自定义函数，用于打印数组、列表。当对一组数字{4，2，6，9}进行排序时，我从printArray函数中得到以下输出:

Intermediate Array: 2 2 6 9 <br>
Intermediate Array: 2 -790123182 6 9<br>
Intermediate Array: 2 -790123182 6 1968115546<br>
Intermediate Array: 2 -790123182 6 1968115546<br>
Intermediate Array: 2 -790123182 6 1968115546<br>
Intermediate Array: 2 -790123182 6 1968115546<br>
Intermediate Array: 2 -790123182 6 1968115546<br>
Intermediate Array: 2 -790123182 6 1968115546<br>

Answer 1

在代码B中，从list到最终的赋值方向错误。试试这个：

/* CODE B */
while ( h <= mid) {
    final[i] = list[h];
    i++; h++;
}

while ( j <= stop ) {
    final[i] = list[j];
    i++; j++;
}
/* End of CODE B */