归并排序实现为何要求数组右索引取size-1而非size？

你的归并排序实现只能在传入右索引为size-1时正常工作，核心问题出在代码的索引约定是「闭区间」，和你尝试传入的「左闭右开」索引逻辑不兼容。

1. 代码的核心索引约定：闭区间 #

你的mergeSort和merge函数全程基于**闭区间[p, r]**设计：

• 递归终止条件if (p < r)：当p == r时，区间内只有一个元素，无需排序
• merge函数里的填充循环for (int k = p; k <= r; k++)：直接遍历从p到r的所有索引（包含两端）
• 左右子数组的长度计算n1 = q - p + 1、n2 = r - q：都是基于闭区间的元素个数公式

2. 传入size作为右索引会直接出错 #

数组的有效索引范围是0到size-1，size本身是越界的无效索引。当你传入r = size时：

• n2 = r - q会计算出比实际右半部分元素数多1的长度
• R[j] = array[q + j]会访问到array[size]这个越界地址，读取到随机垃圾值，导致排序结果混乱，甚至触发内存访问错误

3. 盲目调整偏移量会破坏逻辑一致性 #

你尝试修改偏移量但问题更严重，是因为没有统一整个算法的索引规则。如果想改成「左闭右开」（即r是不包含的右边界），需要一次性修改所有相关逻辑：

• 递归终止条件改为if (p + 1 < r)（区间元素数小于2时终止）
• 中间索引q的计算改为q = (p + r) / 2（整数除法自动向下取整，无需floor）
• 子数组长度改为n1 = q - p、n2 = r - q
• merge中的填充循环改为for (int k = p; k < r; k++)
  只改部分偏移量会让索引对应关系完全错乱，自然问题更严重。

你的实现代码 #

#include <stdlib.h>
#include <limits.h>
#include <math.h>

void mergeSort(int* array, int p, int r)
{
    if (p < r)
    {
        int q = (int)floor((p + r) / 2);
        mergeSort(array, p, q);
        mergeSort(array, q + 1, r);
        merge(array, p, q, r);
    }
}

void merge(int* array, int p, int q, int r)
{

    int n1 = q - p + 1;
    int n2 = r - q;
    int *L = (int*)malloc((n1 + 2) * sizeof(int));
    int *R = (int*)malloc((n2 + 2) * sizeof(int));

    for (int i = 1; i <= n1; i++)
    {
        L[i] = array[p + i - 1];
    }
    for (int j = 1; j <= n2; j++)
    {
        R[j] = array[q + j];
    }
    L[n1+1] = INT_MAX;
    R[n2+1] = INT_MAX;

    int i = 1, j = 1;

    for (int k = p; k <= r; k++) {
        if (L[i] <= R[j]) {
            array[k] = L[i];
            i++;
        }
        else {
            array[k] = R[j];
            j++;
        }
    }
    free(L);
    free(R);
}

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