C 中合并排序、快速排序和结构的奇怪问题

Question

在做 C 编程练习时，我遇到了这个奇怪的问题：合并排序和快速排序算法在我的结构数组中无限循环，试图对其进行排序。
现在，有第三种排序算法可用：插入排序。有了这个，排序工作正常。
所以，我在做这个练习之前测试了所有 3 种算法，它们工作正常（尝试使用 int、double、字符串和字符串数组...）。

我对此一无所知...有什么建议吗？
这是合并排序的代码：

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

并比较函数：

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 是结构类型。

Answer 1

upo_merge_sort_rec 中存在一个简单的错误，导致函数递归的深度远远超过其需要的程度。它应该对从索引 lo 到 hi 的元素进行排序，但其中一个递归调用的较低索引错误地使用了固定的较低索引 0:

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

应该是：

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

C 中合并排序、快速排序和结构的奇怪问题

Strange issue with merge sort, quick sort, and structs in C

c

sorting

algorithm

mergesort