时间复杂度$O(nlogn)$

如果递归到叶子节点就停下来(有效递归层是$logn$),每层的合并都是$O(n)$的,故时间复杂度$O(nlogn)$

#include <iostream>
using namespace std;
constexpr int N = 1e5;
int n;
int a[N+50], t[N+50];//t是辅助数组
void merge_sort(int q[], int l, int r) {
  //递归操作（结束后，子区间内部都是相对有序的，所以需要后续的合并保证整体有序）
  if(l == r) return;
  int mid = (l + r) / 2;
  merge_sort(q, l, mid);
  merge_sort(q, mid + 1, r);
  //合并操作(用了双指针的思想，谁小就加谁，最小数的不仅满足剩下的全局最小，也满足当前区间的最小，
  //所以如果出现左右区间某一个被递归处理完的时候，另外一个区间的数字一定比处理的所有数都大，
  //故后面可以直接补上剩余的数字)
  int ti = l, i = l, j = mid + 1;
  while(i <= mid && j <= r) {
    if(q[i] <= q[j]) {
      t[ti++] = q[i++];
    }
    else {
      t[ti++] = q[j++];
    }
  }
  //哪个区间有剩余就处理剩下的部分
  while(i <= mid) {
    t[ti++] = q[i++];
  }
  while(j <= r) {
    t[ti++] = q[j++];
  }
  //拷贝至原数组
  for(int i = l; i <= r; ++i) {
    q[i] = t[i];
  }
}


int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  cin >> n;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  merge_sort(a, 1, n);
  for(int i = 1; i <= n; ++i) {
    cout << a[i] << " \n"[i==n];
  }
  return 0;
}