归并排序

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto &i : a) {
    cin >> i;
  }
  // [l, r), 升序
  function<void(int, int)> merge_sort = [&](int l, int r) {
    if (r - l <= 1) {
      return;
    }
    int mid = l + ((r - l) >> 1);
    merge_sort(l, mid);
    merge_sort(mid, r);

    // merge
    vector<int> na;
    int i = l, j = mid;
    while (i < mid && j < r) {
      if (a[j] < a[i]) { // 先比较 a[j] < a[i]，可以保证稳定性
        na.emplace_back(a[j]);
        ++j;
      } else {
        na.emplace_back(a[i]);
        ++i;
      }
    }
    while (i < mid) {
      na.emplace_back(a[i]);
      ++i;
    }
    while (j < r) {
      na.emplace_back(a[j]);
      ++j;
    }
    // swap
    for (int i = l; i < r; ++i) {
      a[i] = na[i - l];
    }
  };
  merge_sort(0, a.size());
  for (auto i : a) {
    cout << i << ' ';
  }
  cout << endl;
}