【ACWing】787. 归并排序

题目地址：

https://www.acwing.com/problem/content/789/

给定一个长 n n n的数列，将其从小到大排序。

数据范围：
1 ≤ n ≤ 100000 1\le n\le 100000 1≤n≤100000

用归并排序。代码如下：

#include <iostream>
using namespace std;

const int N = 100010;
int n;
int a[N], tmp[N];

void merge_sort(int l, int r) {
    if (l >= r) return;

    int m = l + (r - l >> 1);
    merge_sort(l, m);
    merge_sort(m + 1, r);

    int idx = 0, i = l, j = m + 1;
    while (i <= m && j <= r) {
        if (a[i] <= a[j]) tmp[idx++] = a[i++];
        else tmp[idx++] = a[j++];
    }

    while (i <= m) tmp[idx++] = a[i++];
    while (j <= r) tmp[idx++] = a[j++];

    for (i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];
}


int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    merge_sort(0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);

    return 0;
}

时间复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn)，空间 O ( n ) O(n) O(n)。