分治与归并排序

💡 打个比方

班里 40 个同学要按身高排队，老师喊"都别动"很乱。换个办法：先两两一组，每 2 个人比一下站好；然后两个小组合并成 4 人小队，排好；再合并成 8 人、16 人、40 人大队。每一步都是"把两个已经排好的队伍，合成一个排好的队伍"。

这就是分治（divide & conquer）：拆——把大问题拆成两个规模减半的小问题；治——小问题小到只剩 1 个元素（天然有序，基本情况）；合——把两个排好的半区合并成一个。

合并是关键：两队都排好序了，每次只要比较两队队头，谁小谁先出列。这样合并一次只比 O(n) 次，而"拆"要拆 log n 层，所以总时间 O(n log n)——比冒泡的 O(n²) 快得多。

🖼️ 大图看明白

📏 怎么写归并排序：只要 3 步

第 1 步：拆——找出中点 mid，把区间 [l, r] 拆成左半 [l, mid] 和右半 [mid+1, r]，分别递归排序。拆到区间只剩 1 个元素（l >= r）就停——基本情况：一个数天然有序。

第 2 步：合——两个半区都排好序了，开一个辅助数组，用两个指针 i、j 分别指着两队头，谁小谁先拷进辅助数组（相等时先拿左边，保证稳定）；哪队先空了，就把另一队剩下的整体拷完。

第 3 步：抄回去——把辅助数组里的结果抄回原数组对应区间，这一层就排好了；一路返回，整个数组就排完了。

💻 C++ 怎么写

int a[105], tmp[105];   // 原数组、辅助数组
// 合并两个已排好序的半区 [l,mid] 和 [mid+1,r]
void merge(int l, int mid, int r) {
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];  // 相等先取左，保证稳定
        else              tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];   // 左边剩下，整体拷
    while (j <= r)   tmp[k++] = a[j++];   // 右边剩下，整体拷
    for (int t = 0; t < k; t++) a[l + t] = tmp[t];  // 抄回原数组
}
// 分治：把 [l,r] 拆一半各自解决，再合并
void mergeSort(int l, int r) {
    if (l >= r) return;         // 基本情况：长度 1 天然有序
    int mid = (l + r) / 2;
    mergeSort(l, mid);          // 治：左半
    mergeSort(mid + 1, r);      // 治：右半
    merge(l, mid, r);           // 合
}

✋ 你来试试