C++如何实现归并排序？分治算法经典案例详解

归并排序是分治算法中最具代表性的排序实现之一。其核心逻辑可以拆成两个动作：先把数组从中间切开，让左右两部分各自排好序；再把两个已经有序的部分合并成一个更大的有序段。由于拆分的过程一直持续到子数组只剩一个元素，而单个元素天然有序，因此合并阶段只需专注处理有序序列的拼接。

一、归并排序的基本原理

分治算法的关键词是“分、治、合”。在归并排序里，“分”指递归地将区间[low, high]划分为[low, mid]和[mid+1, high]；“治”指对这两个子区间分别继续归并排序；“合”则是调用merge函数把两个有序子区间合并回原数组的对应位置。这种结构保证了每一层合并处理的总元素个数都是n，而树的深度为log n，从而得出时间复杂度O(n log n)。

稳定性是归并排序的一大优势。在合并时，如果左半部分和右半部分出现相等的元素，只要优先取左半部分的元素，就能维持原有相对顺序。这一点在业务排序中往往比快排更可靠。另外，归并排序不受到数据分布影响，无论输入是逆序、随机还是几乎有序，比较次数都落在相同量级。

1.1 递归版核心代码

下面给出最基础的递归实现。temp数组用于在合并时暂存结果，避免覆盖原数据。注意mid的计算采用low + (high - low) / 2，可以防止low+high溢出。

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& arr, vector<int>& temp, int low, int mid, int high) {
    int i = low, j = mid + 1, k = low;
    // 双指针把两段有序序列写入temp
    while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    // 处理剩余元素
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= high) temp[k++] = arr[j++];
    // 写回原数组
    for (int p = low; p <= high; p++) arr[p] = temp[p];
}

void mergeSort(vector<int>& arr, vector<int>& temp, int low, int high) {
    if (low >= high) return;
    int mid = low + (high - low) / 2;
    mergeSort(arr, temp, low, mid);
    mergeSort(arr, temp, mid + 1, high);
    merge(arr, temp, low, mid, high);
}

int main() {
    vector<int> arr = {5, 2, 9, 1, 5, 6};
    vector<int> temp(arr.size());
    mergeSort(arr, temp, 0, arr.size() - 1);
    for (int x : arr) cout << x << " ";
    return 0;
}

上述代码在main函数中先构造了与原数组等长的temp，并把它透传至各层递归，这样整个排序过程只分配一次辅助空间。merge函数中的两个while负责把左右两边没比完的尾巴直接接上，逻辑清晰且不易写错。

从调用栈角度看，递归深度为log n，每次merge都会完整扫描当前区间，因此总操作量约为n log n。对于十万级数据，该写法在主流编译器开启优化后通常能在毫秒级完成，而且不会因为数据特点退化。

二、迭代版归并排序

递归写法直观，但在某些嵌入式环境或栈空间受限场景中，递归可能带来溢出风险。迭代版从长度为1的子段开始，不断把步长翻倍进行合并，完全依靠循环控制，不需要函数调用栈。

2.1 自底向上的实现

核心思路是：先令子段长度len=1，每次将相邻两段合并；随后len乘以2，直到len大于等于数组长度。下面的示例用temp做缓冲，并在每轮结束后把数据拷回。

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& arr, vector<int>& temp, int low, int mid, int high) {
    int i = low, j = mid + 1, k = low;
    while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= high) temp[k++] = arr[j++];
    for (int p = low; p <= high; p++) arr[p] = temp[p];
}

void mergeSortIter(vector<int>& arr) {
    int n = arr.size();
    vector<int> temp(n);
    for (int len = 1; len < n; len *= 2) {
        for (int left = 0; left < n; left += 2 * len) {
            int mid = left + len - 1;
            int right = min(left + 2 * len - 1, n - 1);
            if (mid >= right) continue; // 右段不存在则跳过
            merge(arr, temp, left, mid, right);
        }
    }
}

int main() {
    vector<int> arr = {3, 7, 4, 8, 2, 9, 1};
    mergeSortIter(arr);
    for (int x : arr) cout << x << " ";
    return 0;
}

迭代版的关键在于边界处理。当数组长度不是2的幂时，最后一段可能不足len，因此right需要用min来限制，而mid大于等于right时说明只剩左段，无需合并。这样写既安全又高效。

相比递归，迭代版少了函数调用开销，在大规模数据下略有性能优势，同时更容易预测内存使用。如果项目对确定性执行时间敏感，迭代实现往往是更稳妥的选择。

三、常见误区与优化建议

不少人在写merge时直接把结果存回原数组而非temp，导致还没比完的元素被覆盖，输出错乱。务必先合并到辅助数组，再整体拷贝回去。另一个误区是对小规模子数组也递归到底，其实当区间长度小于16时，插入排序的常数更小，可以提前切换。

3.1 混合优化示例

下面演示在递归中嵌入插入排序阈值的做法，能在实际工程中减少约两成比较次数。

#include <iostream>
#include <vector>
using namespace std;

void insertionSort(vector<int>& arr, int low, int high) {
    for (int i = low + 1; i <= high; i++) {
        int key = arr[i], j = i - 1;
        while (j >= low && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void merge(vector<int>& arr, vector<int>& temp, int low, int mid, int high) {
    int i = low, j = mid + 1, k = low;
    while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= high) temp[k++] = arr[j++];
    for (int p = low; p <= high; p++) arr[p] = temp[p];
}

void mergeSort(vector<int>& arr, vector<int>& temp, int low, int high) {
    if (high - low <= 16) {
        insertionSort(arr, low, high);
        return;
    }
    int mid = low + (high - low) / 2;
    mergeSort(arr, temp, low, mid);
    mergeSort(arr, temp, mid + 1, high);
    merge(arr, temp, low, mid, high);
}

int main() {
    vector<int> arr = {10, 3, 8, 1, 6, 2, 9, 4, 7, 5};
    vector<int> temp(arr.size());
    mergeSort(arr, temp, 0, arr.size() - 1);
    for (int x : arr) cout << x << " ";
    return 0;
}

这段代码在子区间长度小于等于16时改走插入排序，既利用了小规模数据局部有序的特性，又保留了归并在大规模时的稳定表现。工程级的std::stable_sort内部就采用了类似思路。

总体来看，掌握C++归并排序不仅是学会一个算法，更是理解分治如何将复杂问题拆成可管理的子问题。熟练之后，你可以把同样的merge框架迁移到外排序、链表排序等场景，扩展性很强。

C++归并排序分治算法merge_sort修改时间：2026-08-04 05:48:37