自底向上合并排序在执行时不做任何事情

Question

int
cmpLong(void *a, void *b) {
    long aa = (long)a;
    long bb = (long)b;
    return aa - bb;
}
int main (int argc, char *argv[]) {
    void **A = (void **)malloc(sizeof(void *) * 5);
    long a = 3, b = 4, c = 1, d = 5, e = 6;
    int n = 0;
    int i;
    A[n++] = (void *)a;
    A[n++] = (void *)b;
    A[n++] = (void *)c;
    A[n++] = (void *)d;
    A[n++] = (void *)e;
    myMergesort(A, n, cmpLong);
    for (i = 0; i < n; i++) {
        printf("%ld\n", (long)A[i]);
    }
    return 0;
}
void merge(void **A, void **B, void **C, \
           int lenA, int lenB, int(cmp)(void *, void *)) {

    int i = 0, j = 0, k = 0;
    while (i < lenA && j < lenB) {
        if(cmp(A[i], B[j]) < 0) {

            C[k++] = A[i++];
        }
        else {
            C[k++] = B[j++];
        }
    }
    while (i < lenA) {
        C[k++] = A[i++];
    }
    while (j < lenB) {
        C[k++] = B[j++];
    }
}


void myMergesort(void **A, int n, int(cmp)(void *, void*)) {
    int i, j, width;
    void **tmp;
    tmp = (void **)malloc(sizeof(void *) * n);
    for (width = 1; width < n; width *= 2) {
        for (i = 0; i < n - width; i = width * 2) {
            if ((i+2*width) > n) {
                int extra = (i+2*width)%width;
                merge(A+i, A+i+width, tmp+i, width, width - extra, cmp);
            }
            else {
                merge(A+i, A+i+width, tmp+i, width, width, cmp);
            }
        }
        for (j = 0; j < n; j++) {
            A[j] = tmp[j];
        }
    }
    return;
}

代码可以编译，但是当它是运行时，什么也没有发生，编译器什么也不做，但它也没有崩溃。几个小时以来我一直在试图找出问题所在，但我似乎无法弄清楚问题是什么

Answer 1

您的问题在这里：

for (width = 1; width < n; width *= 2) {
    for (i = 0; i < n - width; i = width * 2) {

这会导致无限循环，因为 i = width * 2 不会每次都递增 i。

这不一定是您的代码中的唯一问题，但通过解决此问题您应该可以前进。

自底向上合并排序在执行时不做任何事情

Bottom up merge sort doesn't do anything when executed

c

mergesort