While doing my C programming exercises, I've encountered this strange issue: merge sort and quick sort algorithms loop infinitely through my array of structs, trying to sort it.
Now, there is a third sorting algorithm available: insertion sort. With this, the sorting works fine.
So, I tested all 3 algorithms before doing this exercise, and they work fine (tried with int, double, strings and array of strings...).

I have no idea about that... Any suggestion?
This is the code of merge sort:

void upo_merge_sort(void *base, size_t n, size_t size, upo_sort_comparator_t cmp)
{
    assert(base != NULL);
    
    upo_merge_sort_rec(base, 0, n-1, size, cmp);
}

void upo_merge_sort_rec(void *base, size_t lo, size_t hi, size_t size, upo_sort_comparator_t cmp)
{
    if(lo >= hi) { return; }
    
    size_t mid = lo   (hi - lo) / 2;
    
    upo_merge_sort_rec(base, 0, mid, size, cmp);
    upo_merge_sort_rec(base, mid 1, hi, size, cmp);
    upo_merge_sort_merge(base, lo, mid, hi, size, cmp);
}

void upo_merge_sort_merge(void *base, size_t lo, size_t mid, size_t hi, size_t size, upo_sort_comparator_t cmp)
{
    unsigned char *ptr = base;
    unsigned char *aux = NULL;
    size_t n = hi - lo   1;
    size_t i = 0;
    size_t j = mid   1 - lo;
    size_t k;
    
    aux = malloc(n*size);
    if(aux == NULL) {
        perror("Unable to allocate memory for auxiliary vector");
        abort();
    }
    
    memcpy(aux, ptr lo*size, n*size);
    
    for(k = lo; k <= hi;   k) {
        if(i > (mid - lo)) {
            memcpy(ptr k*size, aux j*size, size);
              j;
        }
        else if(j > (hi - lo)) {
            memcpy(ptr k*size, aux i*size, size);
              i;
        }
        else if(cmp(aux j*size, aux i*size) < 0) {
            memcpy(ptr k*size, aux j*size, size);
              j;
        }
        else {
            memcpy(ptr k*size, aux i*size, size);
              i;
        }
    }
    
    free(aux);
}

and compare functions:

int by_track_number_comparator(const void *a, const void *b)
{
    const entry_t *aa = a;
    const entry_t *bb = b;
    int diff = aa->track_num - bb->track_num;
    
    return diff;
}

int by_track_title_comparator(const void *a, const void *b)
{
    const entry_t *aa = a;
    const entry_t *bb = b;
    
    return strcmp(aa->track_title, bb->track_title);
}

entry_t is a struct type.

CodePudding user response：

There is a simple error in upo_merge_sort_rec that makes the function recurse far deeper than it needs to. It should be sorting the elements from index lo to hi inclusive, but the lower index of one of the recursive calls is incorrectly using a fixed lower index of 0:

    upo_merge_sort_rec(base, 0, mid, size, cmp);

should be:

    upo_merge_sort_rec(base, lo, mid, size, cmp);