Bottom up merge sort doesn't do anything when executed

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;
}

The code compiles but when it is run, nothing happens and the compiler doesn't do anything but it also doesn't crash. I have been trying to figure out what the problem is for a few hours and I can't seem to figure what what the problem is

Standard Warning : Please [do not cast](http://stackoverflow.com/q/605845/2173917) the return value of `malloc()` and family in `C`. — Sourav Ghosh, Mar 24 '15 at 13:37
This is a bit much code, so I'm just going to venture a guess. Did you mean for `A[n++] = (void *)a;` and friends to be `A[n++] = &a;`? Notice that I added an address-of operator (`&`). Or are you simply using `void *` as a wide type? — Magnus Hoff, Mar 24 '15 at 13:39
When variable `a` is `void *`, `long aa = (long)a;` takes address in `a` and converts that into `long`. Is that really what you were going to do? — user694733, Mar 24 '15 at 14:01
I believe the original poster indends to cram `long` variables into `void *` data types. Of course it fails if `long` is larger than `void *`. — juhist, Mar 24 '15 at 14:02

score 1 · Accepted Answer · answered Mar 24 '15 at 14:00

Your problem is here:

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

This causes an infinite loop because i = width * 2 does not increment i every time.

Not that this necessarily is the only problem in your code, but by fixing this you should get forward.

Bottom up merge sort doesn't do anything when executed

1 Answers1