题意概括

实现一个归并排序算法，对一个给定大小的整数数组进行升序排序。

数据范围:

• 数组大小 $N$ 满足 $1 \le N \le 10^5$。
• 数组中的每个元素 $a_i$ 满足 $-10^9 \le a_i \le 10^9$。

基础知识

归并排序 (Merge Sort)

归并排序是一种高效、稳定、基于分治思想的排序算法。其核心步骤如下：

1. 分解 (Divide): 将当前待排序的序列递归地二分为两个子序列，直到每个子序列只有一个元素为止。单个元素的序列天然是有序的。
2. 合并 (Conquer/Merge): 将两个已经有序的子序列合并成一个大的有序序列。合并操作是归并排序的关键，通过比较两个子序列的头部元素，将较小的元素放入一个临时数组中，并移动指针，直到一个子序列为空，然后将另一个子序列的剩余部分全部复制到临时数组末尾。最后，将临时数组的内容复制回原数组的对应位置。

复杂度分析:

• 时间复杂度: 归并排序将数组分成两半需要 $O(\log N)$ 层递归，每层递归中的合并操作需要遍历所有元素，时间复杂度为 $O(N)$。因此，总时间复杂度为 $O(N \log N)$。
• 空间复杂度: 合并操作需要一个额外的临时数组来存储排序后的子序列，其大小与待排序序列相当，因此空间复杂度为 $O(N)$。

C++ 代码实现

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 5;

int n;
int a[N], tmp[N];

// 归并排序函数
void ms(int l, int r) {
    if (l >= r) {
        return; // 区间只有一个或没有元素，自然有序
    }

    int mid = (l + r) >> 1;

    // 递归处理左右两个子区间
    ms(l, mid);
    ms(mid + 1, r);

    // 合并操作
    int k = 0;
    int i = l;
    int j = mid + 1;

    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            tmp[k++] = a[j++];
        }
    }

    // 处理剩余的元素
    while (i <= mid) {
        tmp[k++] = a[i++];
    }
    while (j <= r) {
        tmp[k++] = a[j++];
    }

    // 将排好序的临时数组复制回原数组
    for (i = l, j = 0; i <= r; i++, j++) {
        a[i] = tmp[j];
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    ms(0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}