归并排序中的分治

学习目标

本节通过归并排序学习典型分治过程。

归并排序是分治思想的经典应用。它把数组分成两半，分别排序，再把两个有序部分合并成一个整体有序数组。

归并排序的三个阶段

归并排序非常符合分治框架：

分解：把数组拆成左右两半。
解决：递归地对左右两半分别排序。
合并：把两个有序数组合并成一个有序数组。

当数组长度为 0 或 1 时，它本身已经有序，可以作为递归出口。

合并两个有序数组

归并排序的关键是合并过程。

假设有两个已经有序的数组：

左边:  2  5  8
右边:  1  4  9

合并时可以用两个指针分别指向左右数组当前未处理的元素，每次取较小者放入结果中。

最终得到：

1  2  4  5  8  9

归并排序代码

下面实现一个基础版本的归并排序。为了让结构更清晰，示例会使用额外数组保存结果。

vector<int> mergeSort(vector<int> numbers) {
    if (numbers.size() <= 1) {
        return numbers;
    }

    int mid = numbers.size() / 2;
    vector<int> left(numbers.begin(), numbers.begin() + mid);
    vector<int> right(numbers.begin() + mid, numbers.end());

    left = mergeSort(left);
    right = mergeSort(right);

    vector<int> result;
    int i = 0;
    int j = 0;

    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) {
            result.push_back(left[i]);
            i++;
        } else {
            result.push_back(right[j]);
            j++;
        }
    }

    while (i < left.size()) {
        result.push_back(left[i]);
        i++;
    }

    while (j < right.size()) {
        result.push_back(right[j]);
        j++;
    }

    return result;
}

int[] mergeSort(int[] numbers) {
    if (numbers.length <= 1) {
        return numbers;
    }

    int mid = numbers.length / 2;
    int[] left = Arrays.copyOfRange(numbers, 0, mid);
    int[] right = Arrays.copyOfRange(numbers, mid, numbers.length);

    left = mergeSort(left);
    right = mergeSort(right);

    int[] result = new int[numbers.length];
    int i = 0;
    int j = 0;
    int k = 0;

    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result[k++] = left[i++];
        } else {
            result[k++] = right[j++];
        }
    }

    while (i < left.length) {
        result[k++] = left[i++];
    }

    while (j < right.length) {
        result[k++] = right[j++];
    }

    return result;
}

def merge_sort(numbers):
    if len(numbers) <= 1:
        return numbers

    mid = len(numbers) // 2
    left = merge_sort(numbers[:mid])
    right = merge_sort(numbers[mid:])

    result = []
    i = 0
    j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])

    return result

int[] MergeSort(int[] numbers)
{
    if (numbers.Length <= 1)
    {
        return numbers;
    }

    int mid = numbers.Length / 2;
    int[] left = numbers.Take(mid).ToArray();
    int[] right = numbers.Skip(mid).ToArray();

    left = MergeSort(left);
    right = MergeSort(right);

    int[] result = new int[numbers.Length];
    int i = 0;
    int j = 0;
    int k = 0;

    while (i < left.Length && j < right.Length)
    {
        if (left[i] <= right[j])
        {
            result[k++] = left[i++];
        }
        else
        {
            result[k++] = right[j++];
        }
    }

    while (i < left.Length)
    {
        result[k++] = left[i++];
    }

    while (j < right.Length)
    {
        result[k++] = right[j++];
    }

    return result;
}

这段代码的重点不是追求最优工程实现，而是展示归并排序的分治结构：先拆分，再递归排序，最后合并。

归并排序的复杂度

归并排序每一层合并都需要处理所有 $n$ 个元素。

数组每次被拆成两半，因此递归层数大约是 $\log n$ 。每层成本是 $O(n)$ ，层数是 $O(\log n)$ ，所以总时间复杂度是 $O(n \log n)$ 。

由于合并时需要额外数组，空间复杂度通常是 $O(n)$ 。递归调用栈还会带来 $O(\log n)$ 的深度开销，但主要额外空间通常来自合并数组。

归并排序的特点

归并排序的特点包括：

时间复杂度稳定，最好、最坏和平均情况通常都是 $O(n \log n)$ 。
合并时可以保持相等元素的相对顺序，因此可以实现稳定排序。
需要额外空间，通常是 $O(n)$ 。
非常适合用来理解分治思想。

后续学习排序章节时，还会把归并排序和快速排序、堆排序等算法放在一起比较。

本节小结

归并排序是分治思想的经典例子。

它先把数组不断拆成更小部分，再递归排序，最后合并有序结果。它的时间复杂度是 $O(n \log n)$ ，空间复杂度通常是 $O(n)$ 。理解归并排序后，分治的“拆分、解决、合并”框架会更加清晰。