归并排序算法c++代码

归并排序是一种分治算法，它将数组分成两半递归地排序，然后合并结果。以下是使用C++实现归并排序的基本步骤：

#include <iostream>
#include <vector>

// 合并两个已排序的区间
void merge(std::vector<int>& arr, int left, int mid, int right) {
    std::vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 将剩余未添加到temp的元素复制回原数组
    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    // 把临时数组的内容复制回原数组
    for (i = left; i <= right; i++) {
        arr[i] = temp[i - left];
    }
}

// 归并排序函数
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); // 合并两个已排序的部分
    }
}

int main() {
    std::vector<int> nums = {9, 7, 5, 11, 12, 2, 14, 3};
    int n = nums.size();
    mergeSort(nums, 0, n - 1);
    for (auto num : nums) {
        std::cout << num << " ";
    }
    return 0;
}