如何将C语言实现的升序归并排序修改为降序归并排序

问题根因 #

归并排序是递归分层执行的，每一次merge操作的前提是：传入的左半段[low, mid]和右半段[mid+1, high]都已经按照目标排序规则完成排序。
你只修改了合并完成后倒序复制回原数组的逻辑，会导致当前层合并完返回给上层的子数组不符合上层合并的大小比较逻辑，上层合并时拿到的子数组既不是升序也不是统一的降序，最终结果自然不符合预期。

最简正确修改方案 #

只需要修改merge函数中合并两个子数组的比较条件，把原来优先取更小元素的逻辑改成优先取更大的元素即可，其余代码不需要调整：
把原来的判断条件

if (A[i] < A[j])

修改为

if (A[i] > A[j])

修改后的完整merge函数如下：

void merge(int A[] , int mid, int low, int high){
    int B[high+1];
    int i = low, j = mid+1, k = low;
    while (i <= mid && j <= high)
    {
        // 仅修改此处比较符号，优先取更大的元素放入临时数组
        if (A[i] > A[j])
        {
            B[k] = A[i];
            k++;
            i++;
        }
        else
        {
            B[k] = A[j];
            k++;
            j++;
        }
    }
    
    while (i<=mid)
    {
        B[k] = A[i];
        k++;
        i++;
    }
    while (j<=high)
    {
        B[k] = A[j];
        k++;
        j++;
    }

    // 复制逻辑不需要修改
    for (int i = low; i <= high; i++)
    {
        A[i] = B[i];
    }
}

mergesort函数不需要做任何修改，直接运行即可得到降序排列的结果。

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