泛型归并排序处理结构体指针数组失效问题排查

以下是最可能导致排序结果错误的核心问题及排查方向：

1. 比较函数的参数传递逻辑错误 #

你的compQueries/compEvents是为指针数组设计的，签名需与qsort的比较函数一致：

int compQueries(const void* a, const void* b) {
    // a、b是指向数组元素的指针，即Query**类型
    const Query* q1 = *(const Query**)a;
    const Query* q2 = *(const Query**)b;
    // 此处编写具体比较逻辑
}

如果泛型归并排序函数调用比较函数时，错误传递指针指向的结构体地址（即直接传*(void*)elem_addr），而非数组元素本身的地址（指针的地址），会直接导致比较逻辑完全失效。

检查归并排序中调用比较函数的代码，正确的调用方式应为：

// left_elem、right_elem是指向数组中指针元素的char*地址
int cmp_result = comp(left_elem, right_elem);

而非错误的：

// 错误：传递了结构体地址，而非指针的地址
int cmp_result = comp(*left_elem, *right_elem);

2. 元素拷贝/交换的内存操作错误 #

你排序的是指针数组，每个元素大小为sizeof(Query*)或sizeof(Event*)，归并过程中需拷贝的是指针本身，而非指针指向的结构体。重点检查：

• 临时数组内存分配：是否按elemSize * 元素数量分配？例如：

  char* temp = malloc(elemSize * (right - left + 1));
  

• memcpy的参数：拷贝元素时是否使用了正确的大小？例如：

  memcpy(temp + i*elemSize, (char*)base + left + i*elemSize, elemSize);
  

• 交换元素逻辑：是否以elemSize为单位交换，而非结构体大小？

3. 泛型地址计算错误 #

泛型代码中必须通过char*进行地址偏移（void*不支持算术运算），检查元素地址计算逻辑：
正确的地址计算：

// 获取数组中第i个元素的地址
char* elem_addr = (char*)base + i * elemSize;

若误用void*直接偏移、或用结构体大小替代elemSize，会导致访问错误内存位置，引发排序混乱。

4. 递归边界与归并逻辑的细节偏差 #

虽然单一类型归并排序正常，但泛型改造时可能误改边界处理：

• 确认mid计算正确：mid = left + (right - left)/2，避免整数溢出。
• 确认归并时左右区间划分正确：左半部分[left, mid]，右半部分[mid+1, right]。

验证建议 #

可以在泛型归并排序中加入调试逻辑：

• 调用比较函数时，打印传入的参数值与比较结果，验证是否符合预期。
• 归并前后打印数组中关键指针的地址（或结构体的核心字段值），确认指针在拷贝过程中未被篡改。

内容的提问来源于stack exchange，提问作者Neutrino