代码

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100001];
int t[100001];
// C++ Version
void merge(int ll, int rr) {
  // 用来把 a 数组 [ll, rr - 1] 这一区间的数排序。 t
  // 数组是临时存放有序的版本用的。
  if (rr - ll <= 1) return;
  int mid = ll + ((rr - ll) >> 1);
  merge(ll, mid);
  merge(mid, rr);
  int p = ll, q = mid, s = ll;
  while (s < rr) {
    if (p >= mid || (q < rr && a[p] > a[q])) {
      t[s++] = a[q++];
      // ans += mid - p;
    } else
      t[s++] = a[p++];
  }
  for (int i = ll; i < rr; ++i) a[i] = t[i];
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    n = 5;
    a[1] = 4;
    a[2] = 3;
    a[3] = 2;
    a[4] = 5;
    a[5] = 1;
    merge(1, n);
    for (int i = 1; i <= n; ++i) {
        cout << a[i] << ' ' ;
    }
    cout << endl;
}

评测结果