野牛程序员讲少儿编程：归并排序来啦，拆了又合的排序魔法！

🎉 野牛程序员讲少儿编程：归并排序来啦，拆了又合的排序魔法！ 🧙‍♂️✨

📢 各位大小程序员，请系好安全带，今天带来一个超级聪明、逻辑缜密、又带点“分裂”气质的排序选手——归并排序（Merge Sort）！

它不靠拳头拼蛮力，不像冒泡一样天天打擂台，不像选择插入天天找最小。它走的是高端路线：分而治之，动脑不动手！

🎁 归并排序的核心思想：拆！拆！拆！合！合！合！

📌 用一句话总结就是：

先拆成最小块，再合并成有序数组。

🎬 一步一步讲解给小朋友听听：

🪓 步骤一：分（Divide）

把原始数组一劈两半！
比如数组是 [38, 27, 43, 3, 9, 82, 10]
咔！劈成两部分：

[38, 27, 43]   和   [3, 9, 82, 10]

继续劈下去！直到每一份只剩下1个元素为止👇
（1个元素自己本身就是有序的）

🪢 步骤二：治（Conquer）

从最小的两个开始合并，合并时注意排序！

比如：
[38] 和 [27] 合并成 [27, 38]
[3] 和 [9] 合并成 [3, 9]

然后再逐步合并更大的部分，最后合成完整有序数组！

🎯 举个例子：

排序 [4, 1, 6, 2] 的过程如下：

🧨 拆解过程：

[4, 1, 6, 2]
→ [4, 1] 和 [6, 2]
→ [4] [1] [6] [2]

🔧 合并过程：

→ [1, 4] 和 [2, 6]
→ [1, 2, 4, 6] ✅ 排序完成！

🧠 代码怎么写？（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)
        return;

    int mid = left + (right - left) / 2;

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

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int size = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, size - 1);

    cout << "排序结果：";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";

    return 0;
}

🔍 小贴士时间

🧩 时间复杂度：O(n log n)，超级快！
🧩 空间复杂度：O(n)，因为用了临时数组
🧩 排序稳定，适合大数据、追求精度的场合！

🧒 小朋友怎么记？

• 像拆拼图一样把数组拆成小块

• 然后像拼拼图一样一块块有序拼回去

• 拼得越整齐，程序越开心！🧩