合并排序算法运行不正常

Question

合并排序算法未按预期运行。输出值未按升序完全排序。有些值乱序，这表明存在错误。

#include <stdio.h>
#include <stdlib.h>

void merge(int *L, int *R, int *a, int nL, int nR) {
    int i, j, k;
    i = j = k = 0;

    while ((i < nL) && (j < nL)) {
        if (L[i] < R[j]) {
            a[k] = L[i];
            ++i;
        } else {
            a[k] = R[j];
            ++j;
        }
        ++k;
    }

    while (i < nL) {
        a[k] = L[i];
        ++i;
        ++k;
    }

    while (j < nR) {
        a[k] = R[j];
        ++j;
        ++k;
    }
}

void mergeSort(int *a, int n) {
    if (n < 2)
        return;

    int i, mid, *L, *R;

    mid = n / 2;

    L = (int *)malloc(mid * sizeof(int));
    R = (int *)malloc((n - mid) * sizeof(int));

    for (i = 0; i < mid; ++i) {
        L[i] = a[i];
    }

    for (i = mid; i < n; ++i) {
        R[i - mid] = a[i];
    }

    mergeSort(L, mid);
    mergeSort(R, n - mid);

    merge(L, R, a, mid, n - mid);

    free(L);
    free(R);
}

int main() {
    int i, n, *a;

    scanf("%d", &n);

    a = (int *)malloc(n * sizeof(int));

    for (i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }

    mergeSort(a, n);

    for (i = 0; i < n; ++i) {
        printf("%d ", a[i]);
    }

    free(a);

    return 0;
}

例如，对于以下输入：10 10 9 8 7 6 5 4 3 2 1

我应该得到这些输出：1 2 3 4 5 6 7 8 9 10

但是输出不是按升序排列的。输出是：1 3 4 5 2 6 8 9 10 7

Answer 1

不确定它是否涵盖了所有问题但是

while((i < nL) && (j < nL))

应该是

while((i < nL) && (j < nR))
                        ^
                        note

合并排序算法运行不正常

Merge sort algorithm is not functioning properly

c

sorting

merge

mergesort

divide-and-conquer