🧩 归并排序 (Merge Sort)

归档: #Algorithm #Sorting #Advanced

核心心法: "先拆后合" —— 像拉链一样，把两个有序的链条合并成一条。

🧠 核心思想 (后序遍历)

归并的本质是二叉树的后序遍历。

1. 分 (Divide)：一刀两断，递归切分直到子数组只剩 1 个元素（天然有序）。
2. 合 (Merge)：将两个有序的子数组合并成一个大的有序数组。

🎨 图解演示

请选择排序模式

65

30

82

10

45

22

90

15

77

55

33

88

5

60

28

95

12

40

Auxiliary Array (临时空间)⬇️ Copy To Temp / Copy Back ⬆️

左组 (Blue)

右组 (Purple)

已合并 (Green)

💻 代码实现 (C++)

// 对应动画中的 "递归模式"
// 核心思路：分而治之，先递归拆分到最小，再回溯合并
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        if (nums.empty()) return nums;
        vector<int> temp(nums.size()); // 提前开辟空间，避免递归中频繁申请
        mergeSort(nums, 0, nums.size() - 1, temp);
        return nums;
    }

    // 递归主函数
    void mergeSort(vector<int>& nums, int left, int right, vector<int>& temp) {
        if (left >= right) return;

        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid, temp);      // 排左边
        mergeSort(nums, mid + 1, right, temp); // 排右边

        merge(nums, left, mid, right, temp);   // 合并
    }

    // 合并两个有序区间
    void merge(vector<int>& nums, int left, int mid, int right, vector<int>& temp) {
        int i = left;
        int j = mid + 1;
        int t = 0; // temp 的临时指针

        // 双指针比大小
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[t++] = nums[i++];
            } else {
                temp[t++] = nums[j++];
            }
        }

        // 处理剩余元素
        while (i <= mid) temp[t++] = nums[i++];
        while (j <= right) temp[t++] = nums[j++];

        // 抄回原数组 (注意这里要从 temp 抄回 nums)
        t = 0;
        while (left <= right) {
            nums[left++] = temp[t++];
        }
    }
};

// 对应动画中的 "迭代模式"
// 核心思路：从 width=1 开始，两两合并，再四四合并... 直到 width >= n
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> tmp(n);
        
        // width 代表子数组长度：1 -> 2 -> 4 -> 8 ...
        for (int width = 1; width < n; width *= 2) {
            // 遍历数组，每次处理两个 width 长度的块
            for (int i = 0; i < n; i += 2 * width) {
                int left = i;
                int mid = min(i + width - 1, n - 1);
                int right = min(i + 2 * width - 1, n - 1);
                
                // 只有当存在右半部分时才需要合并
                if (mid < right) {
                    merge(nums, tmp, left, mid, right);
                }
            }
        }
        return nums;
    }

    // 合并函数 (与递归版逻辑一致)
    void merge(vector<int>& nums, vector<int>& tmp, int left, int mid, int right) {
        int i = left, j = mid + 1, k = left;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
            else tmp[k++] = nums[j++];
        }
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= right) tmp[k++] = nums[j++];
        
        for (int p = left; p <= right; p++) nums[p] = tmp[p];
    }
};

📊 复杂度分析

维度	数值	说明
时间 (平均)		雷打不动，非常稳
时间 (最差)		不受数据分布影响
空间		需要一个额外的 temp 数组 (这是缺点)
稳定性	✅ 稳定	合并时左边先入，保证了稳定性

💡 适用场景

• 链表排序：唯一的神！不需要额外空间，只改指针。

• 大数据外部排序：内存放不下时，切分文件排好再 Merge。

• 需要稳定排序时：比如按“分数”排序，分数一样要保持“学号”顺序。