归并排序

#include <iostream>
#include <vector>

// 合并两个有序子数组：arr[left..mid] 和 arr[mid+1..right]
void merge(std::vector<int>& arr, int left, int mid, int right, std::vector<int>& temp) {
    int i = left;      // 左子数组的起点
    int j = mid + 1;  // 右子数组的起点
    int k = left;      // 辅助数组 temp 的写入索引

    // 比较两个子数组的元素，将较小者依次放入 temp 中
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) { // <= 保证了算法的稳定性
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 处理左子数组可能剩余的元素
    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    // 处理右子数组可能剩余的元素
    while (j <= right) {
        temp[k++] = arr[j++];
    }

    // 将合并后的结果从 temp 拷贝回原数组 arr
    for (int p = left; p <= right; ++p) {
        arr[p] = temp[p];
    }
}

// 归并排序主递归函数
void mergeSortRecursive(std::vector<int>& arr, int left, int right, std::vector<int>& temp) {
    // 递归基线条件：子数组长度小于等于 1
    if (left >= right) {
        return;
    }

    // 计算中点，防止 (left + right) 溢出
    int mid = left + (right - left) / 2;

    // 递归对左右两半部分排序
    mergeSortRecursive(arr, left, mid, temp);
    mergeSortRecursive(arr, mid + 1, right, temp);

    // 将排序好的两部分合并
    merge(arr, left, mid, right, temp);
}

// 对外暴露的接口
void mergeSort(std::vector<int>& arr) {
    if (arr.empty()) return;
    std::vector<int> temp(arr.size());
    mergeSortRecursive(arr, 0, arr.size() - 1, temp);
}

int main() {
    std::vector<int> nums = {38, 27, 43, 3, 9, 82, 10};

    std::cout << "排序前: ";
    for (int num : nums) std::cout << num << " ";
    std::cout << std::endl;

    mergeSort(nums);

    std::cout << "排序后: ";
    for (int num : nums) std::cout << num << " ";
    std::cout << std::endl;

    return 0;
}