归并排序

#include <iostream>
using namespace std;

long long n, a[1000010];

void merge_sort(int l, int r) {
    if (l == r) return;    //如果只有一个数据就要开始往前返回了
    int mid = (l + r) >> 1;    //找中间值
    merge_sort(l, mid);
    merge_sort(mid + 1, r);    //把数据分成两段排序
    int k = l, i = l, j = mid + 1, temp[100010];    //因为左边和右边已经排完序了， 所以可以用双指针，哪边少哪边加到临时数组里边
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];    //把剩余的都加到临时数组里边
    for (int i = l; i <= r; i++) a[i] = temp[i];    //把原本的数组更新
}

int main () {
    scanf("%lld\n", &n);
    for (int i = 1; i <= n; i++) scanf("%lld ", a + i);
    merge_sort(1, n);
    for (int i = 1; i <= n; i++) printf("%lld ", a[i]);    //最后就可以输出了
    return 0;
}