基于CLRS的归并排序算法介绍，带倒置计数，基于C++

归并排序是一种经典的排序算法，它基于分治策略将一个大问题分解为多个小问题，然后将小问题的解合并起来得到最终的解。该算法的核心思想是将待排序的数组不断地二分，直到每个子数组只有一个元素，然后再将这些子数组两两合并，直到最终得到有序的数组。

归并排序的步骤如下：

将待排序的数组递归地二分为两个子数组，直到每个子数组只有一个元素。
对每个子数组进行合并操作，将两个有序的子数组合并为一个有序的数组。
重复步骤2，直到最终得到完全有序的数组。

归并排序的倒置计数是指在排序过程中统计数组中的倒置对数，即数组中的逆序对数量。倒置对是指在数组中，如果i < j 且 A[i] > A[j]，则称(A[i], A[j])为一个倒置对。倒置计数可以用于衡量数组的有序程度。

C++实现归并排序的代码如下：

#include <iostream>
#include <vector>

using namespace std;

// 合并两个有序数组
void merge(vector<int>& nums, int left, int mid, int right, int& count) {
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
            count += mid - i + 1;  // 统计倒置对数
        }
    }

    while (i <= mid) {
        temp[k++] = nums[i++];
    }

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

    for (int p = 0; p < temp.size(); p++) {
        nums[left + p] = temp[p];
    }
}

// 归并排序
void mergeSort(vector<int>& nums, int left, int right, int& count) {
    if (left >= right) {
        return;
    }

    int mid = left + (right - left) / 2;
    mergeSort(nums, left, mid, count);
    mergeSort(nums, mid + 1, right, count);
    merge(nums, left, mid, right, count);
}

// 归并排序入口函数
vector<int> mergeSort(vector<int>& nums) {
    int count = 0;
    mergeSort(nums, 0, nums.size() - 1, count);
    return nums;
}

int main() {
    vector<int> nums = {5, 2, 6, 1, 3, 4};
    vector<int> sortedNums = mergeSort(nums);

    cout << "排序结果：";
    for (int num : sortedNums) {
        cout << num << " ";
    }
    cout << endl;

    cout << "倒置对数：" << count << endl;

    return 0;
}

归并排序的时间复杂度为O(nlogn)，其中n为待排序数组的长度。它是一种稳定的排序算法，适用于各种规模的数组排序。

归并排序的应用场景包括但不限于：