归并排序（Merge Sort）中merge函数为何初始化k=l？

merge函数的核心作用是：把原数组中两个相邻的有序子区间[l, mid]和[mid+1, r]，合并成一个有序区间，再将结果放回原数组的[l, r]位置。

变量k是「原数组中待写入合并元素的位置指针」，初始化k = l的原因很明确：

• 我们要填充的目标区间从l开始，必须从这个起点依次写入合并后的元素，才能让合并后的有序区间精准覆盖原来的无序子区间，不会破坏数组中其他已经排序好的部分。
• 如果错误地把k初始化为0或其他值，会导致合并后的元素被写到数组错误位置，要么覆盖前面已排序元素，要么让当前子区间的排序结果错位，最终整个归并排序逻辑彻底失效。

结合一段典型的merge代码来看更直观：

void merge(int arr[], int l, int mid, int r) {
    int n1 = mid - l + 1;
    int n2 = r - mid;
    int left[n1], right[n2];

    // 将原数组的左右子区间复制到临时数组
    for (int i = 0; i < n1; i++)
        left[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        right[j] = arr[mid + 1 + j];

    int i = 0, j = 0;
    int k = l; // 从目标区间的起点开始写入

    // 合并两个有序临时数组到原数组
    while (i < n1 && j < n2) {
        arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
    }

    // 处理左临时数组的剩余元素
    while (i < n1) {
        arr[k++] = left[i++];
    }
    // 处理右临时数组的剩余元素
    while (j < n2) {
        arr[k++] = right[j++];
    }
}

简言之，k的初始化值必须和当前要处理的子区间起点对齐，这是归并排序分治逻辑的必然要求——每一次merge只负责修复当前子区间的有序性，不能干扰数组的其他部分。

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