《野牛程序员讲少儿编程算法》系列迎来新主角：归并排序

? 归并排序是啥？

简单说，归并排序像“拼图高手”?
先把一堆乱七八糟的拼图分成一小块一小块（拆！）
等每一块都整整齐齐了，再一块一块拼起来（并！）

就像收拾房间：
? “咱先把玩具按种类分好，再一个一个放进盒子里！”

? 思路（野牛程序员温馨提示）：

? 拆分阶段（分）：

• 一直把数组对半分，分成一个个小单元，直到每个“单元”里只有一个数。

? 合并阶段（并）：

• 从最小的单元开始，两个两个合并，每次合并都保证结果是有序的。

过程听起来像在“开双倍副本”：
?【拆】→【拆】→【拆】→ ?【合】→【合】→ ?【合并完成】

? 举个小例子：

对数组 [8, 4, 5, 7, 1, 3, 6, 2] 进行归并排序：

1. 分成：[8,4,5,7] 和 [1,3,6,2]

2. 再分：[8,4] [5,7] 和 [1,3] [6,2]

3. 最小单位：[8][4][5][7][1][3][6][2]

现在开始合并：

• 合并：[4,8], [5,7], [1,3], [2,6]

• 再合并：[4,5,7,8], [1,2,3,6]

• 最后合并：[1,2,3,4,5,6,7,8]

? 排完了！

? C++ 代码来了！（加了点解说，小朋友也能读懂）

#include <iostream>
using namespace std;

// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1; // 左边长度
    int n2 = right - mid;    // 右边长度

    // 创建临时数组
    int L[n1], R[n2];

    // 拷贝左右两个数组
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    // 合并两个临时数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }

    // 如果左边还有剩
    while (i < n1) arr[k++] = L[i++];

    // 如果右边还有剩
    while (j < n2) arr[k++] = R[j++];
}

// 归并排序递归实现
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // 防止溢出

        mergeSort(arr, left, mid);    // 排左边
        mergeSort(arr, mid + 1, right); // 排右边
        merge(arr, left, mid, right); // 合并
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {8, 4, 5, 7, 1, 3, 6, 2};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前：";
    printArray(arr, size);

    mergeSort(arr, 0, size - 1);

    cout << "排序后：";
    printArray(arr, size);

    return 0;
}

?‍♀️ 为什么它棒棒哒？

✅ 归并排序的时间复杂度稳定是 O(n log n)，不怕最坏情况
✅ 适合大规模数据，很多高端编程比赛就靠它上分！
✅ 逻辑清晰，帮助理解“递归”、“合并”思想，数学思维 up⬆️

? 小问题考考你：

数组 [9, 5, 1, 8, 3] 用归并排序会分几次？每次合并后会变成什么？
在纸上画一画，试着给爸爸妈妈讲一讲，看懂没！