归并排序

#include <bits/stdc++.h>

using namespace std;

const int len = 1e5 + 5;
int N, nums[len], temp[len];

void merge_sort(int n[], int l, int r) {
    if (l >= r) return;
    int mid = (l + r) >> 1;
    merge_sort(n, l, mid);
    merge_sort(n, mid + 1, r);
    int index = 0, left = l, right = mid + 1;
    while (left <= mid && right <= r) {
        if (n[left] < n[right]) temp[index++] = n[left++];
        else temp[index++] = n[right++];
    }
    while (left <= mid) temp[index++] = n[left++];
    while (right <= r) temp[index++] = n[right++];
    for (int i = l, k = 0; i <= r; ++i) n[i] = temp[k++];
}

int main() {
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> nums[i];
    merge_sort(nums, 0, N - 1);
    for (int i = 0; i < N; ++i) cout << nums[i] << " ";
    return 0;
}