#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int cnt = 0; // 计数器,表示逆序对的个数
// left = [l, m-1] right = [m, r]
void Merge(vector<int>& arr, int l, int m, int r) {
int leftSize = m - l;
int rightSize = r - m + 1;
int *left = new int[leftSize];
int *right = new int[rightSize];
for (int i = l; i < m; i++) {
left[i - l] = arr[i];
}
for (int i = m; i <= r; i++) {
right[i - m] = arr[i];
}
int i = 0;
int j = 0;
int k = l;
while (i < leftSize && j < rightSize) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
// left[i] > right[j] && i < j 构成逆序
// 此时左区间元素大于右区间元素,则左区间的所有剩余元素都与右区间的当前元素构成逆序对
cnt += (leftSize - i);
}
}
while (i < leftSize) {
arr[k++] = left[i++];
}
while (j < rightSize) {
arr[k++] = right[j++];
}
delete[] left;
left = nullptr;
delete[] right;
right = nullptr;
}
void _MergeSort(vector<int> &arr, int l, int r) {
if (l >= r) {
return;
}
int m = (r - l) / 2 + l;
_MergeSort(arr, l, m);
_MergeSort(arr, m + 1, r);
Merge(arr, l, m + 1, r);
}
void MergeSort(vector<int> &arr) {
_MergeSort(arr, 0, arr.size() - 1);
}
int main() {
vector<int> arr = {1, 3, 2, 5, 4, 7, 6};
auto f = [] (int x) {cout << x << " ";};
for_each(arr.begin(), arr.end(), f); cout << endl;
MergeSort(arr);
for_each(arr.begin(), arr.end(), f); cout << endl;
cout << "the number of reverse number pair is " << cnt << endl;
return 0;
}