经典排序算法：归并排序 (Merge Sort)

什么是归并排序？

归并排序是一种高效的、基于分治思想的排序算法。它将一个大问题分解为多个小问题来解决。其核心操作是“归并”，即将两个已经有序的序列合并成一个有序序列。

算法步骤

1. 分解 (Divide): 将当前数组一分为二，直至每个子数组只有一个元素（此时可认为是有序的）。
2. 解决 (Conquer): 递归地对两个子数组进行归并排序。
3. 合并 (Combine): 将两个已排序的子数组合并成一个大的有序数组。

代码实现 (C++)

#include <iostream>
#include <vector>

// 合并两个有序子数组
void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    std::vector<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];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 归并排序主函数
void mergeSort(std::vector<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);
    }
}

复杂度分析

• 时间复杂度: O(n log n)。分解过程是 log n，每次合并是 O(n)。
• 空间复杂度: O(n)。需要一个辅助数组来存储合并中的元素。
• 稳定性: 归并排序是稳定的排序算法。