实现通用归并排序时，如何让memcmp支持有符号整数比较？

问题根源很明确：memcmp是按字节以无符号值逐位比较的，而有符号整数用补码存储时，负数的最高位是1，对应的字节无符号值会比正数的高位字节大，导致memcmp误判负数比正数大。

你可以通过调整元素的比特位和字节顺序，让memcmp能正确识别有符号整数的大小关系，具体步骤如下：

实现步骤 #

1. 排序前预处理数组 #

统一字节序为大端

不管你的系统是大端还是小端，先把每个元素的字节顺序反转，让最高位字节放在内存最前面。这样memcmp会先比较最高位，和数值大小的判断逻辑一致。通用的字节反转函数可以这么写：

void reverse_bytes(void *elem, size_t size) {
    unsigned char *start = (unsigned char *)elem;
    unsigned char *end = start + size - 1;
    while (start < end) {
        unsigned char temp = *start;
        *start = *end;
        *end = temp;
        start++;
        end--;
    }
}

翻转最高位符号位

对每个元素的第一个字节（大端下的最高位字节）执行异或0x80操作。这一步会把有符号数的符号位反转：原来的负数（最高位1）变成最高位0，正数（最高位0）变成最高位1，同时保持所有元素的相对大小关系不变。代码如下：

unsigned char *high_byte = (unsigned char *)elem;
*high_byte ^= 0x80;

2. 执行归并排序 #

这时候直接用memcmp比较预处理后的元素就行，它的返回值会正确反映原始有符号整数的大小关系。

3. 排序后恢复原始数组 #

• 再次对每个元素的第一个字节异或0x80，把符号位还原回去。
• 再次调用reverse_bytes函数，把字节顺序恢复成系统原本的样子。

注意事项 #

• 这个方案只适用于有符号原始类型（比如默认有符号的char、int、long等），如果传入无符号类型（比如unsigned int、byte），排序结果会出错。
• 虽然多了字节反转和比特位翻转的开销，但完全满足你不想传比较函数、不想按类型分支的需求。

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