算法刷题系列（三十四）：分治——拆分子问题并合并结果

算法刷题系列（三十四）：分治——拆分子问题并合并结果

分治不是“把输入切开”就结束。一个完整的分治算法需要三个环节：把问题拆成规模更小的同类子问题，递归求解，再用可控的合并过程得到原问题答案。归并排序能很好地展示三者如何配合。

归并排序的结构

对半切分数组，分别排序左右区间，最后线性合并。定义 sort(left, right) 的含义为：调用返回时，闭区间 [left,right] 已按升序排列。长度为零或一时本来就有序，是递归基线；两个有序子区间可以用双指针合并。

合并时，i 和 j 分别指向左右区间尚未处理的最小元素。每一步取较小者放入临时数组，直到一侧耗尽，再复制另一侧剩余元素。循环不变量是：临时数组始终是两个子区间已处理元素的有序合并。

Java 实现

public class MergeSort {
    public static void sort(int[] values) {
        if (values == null) {
            throw new IllegalArgumentException("values must not be null");
        }
        int[] buffer = new int[values.length];
        sort(values, buffer, 0, values.length);
    }

    private static void sort(int[] values, int[] buffer, int left, int right) {
        if (right - left <= 1) {
            return;
        }
        int middle = left + (right - left) / 2;
        sort(values, buffer, left, middle);
        sort(values, buffer, middle, right);
        merge(values, buffer, left, middle, right);
    }

    private static void merge(
        int[] values, int[] buffer, int left, int middle, int right
    ) {
        int i = left, j = middle, out = left;
        while (i < middle && j < right) {
            if (values[i] <= values[j]) {
                buffer[out++] = values[i++];
            } else {
                buffer[out++] = values[j++];
            }
        }
        while (i < middle) {
            buffer[out++] = values[i++];
        }
        while (j < right) {
            buffer[out++] = values[j++];
        }
        for (int index = left; index < right; index++) {
            values[index] = buffer[index];
        }
    }
}

这里使用半开区间 [left,right)，区间长度直接是 right - left，左右两半分别为 [left,middle) 和 [middle,right)，边界不需要额外加减一。

Python 实现

def merge_sort(values: list[int]) -> list[int]:
    if len(values) <= 1:
        return values.copy()
    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    merged: list[int] = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

assert merge_sort([8, 3, 3, -1, 5]) == [-1, 3, 3, 5, 8]
assert merge_sort([]) == []

正确性与复杂度

基线区间长度不超过一，天然有序。假设递归返回后左右区间各自有序，合并过程每次取两侧未处理元素的较小者，因此输出保持有序且不丢失元素；合并结束后整个区间有序。由递归归纳，最终全数组有序。

递归满足 T(n)=2T(n/2)+O(n)，所以时间为 O(n log n)，额外数组空间为 O(n)，递归栈为 O(log n)。Python 切片还会创建子数组，空间同样是线性量级，但有额外分配；若需原地控制分配，可改用索引和共享缓冲区。

常见错误与边界

• 空数组与单元素数组都应直接返回。
• 合并两段时必须复制尚未耗尽一侧的尾部。
• 不要在递归中使用含义不一致的左右边界；半开区间和闭区间任选其一，但全程统一。
• 相等时优先取左侧（<=），归并排序便是稳定的：相等元素的原始相对顺序保留。
• 分治适用于子问题规模缩小、子问题答案可组合的情况；拆分后若仍需比较所有左右元素，合并成本可能高于线性，复杂度也会随之变化。

分析新的分治题时，可以先写出递归函数的精确定义与基线，再单独论证合并步骤的正确性，最后列出递推式。