1#include<iostream>
2#include<algorithm>
3#include<vector>
4#include "stdio.h"
5#include "time.h"
6using namespace std;
7
8int a[10000005] = {0};
9
10// 合并两个有序数组段的函数
11void merge(int a[], int left, int mid, int right) {
12    int t[105] = {0}; // 创建一个临时数组用于存储合并后的有序序列
13    int lp = left; // lp是左半部分的起始索引
14    int rp = mid + 1; // rp是右半部分的起始索引
15    int si = left; // si是用于追踪当前要插入元素到临时数组t的索引
16    
17    // 遍历左右两部分，直到一个达到终点
18    while (si <= right) {
19        // 如果左半部分已完全处理完毕，或者右半部分当前元素小于左半部分当前元素
20        if (lp > mid || (rp <= right && a[lp] > a[rp])) {
21            t[si] = a[rp]; // 将右半部分当前元素拷贝到临时数组
22            rp++; // 移动右半部分的索引
23        }
24        else {
25            t[si] = a[lp]; // 否则，将左半部分当前元素拷贝到临时数组
26            lp++; // 移动左半部分的索引
27        }
28        si++; // 移动临时数组的索引
29    }
30    
31    // 将临时数组中排序后的元素拷贝回原数组a
32    for (int i = left; i <= right; i++) {
33        a[i] = t[i];
34    }
35}
36
37// 归并排序的递归实现
38void merge_sort(int a[], int left, int right) {
39    if (right <= left) {
40        return; // 如果当前数组段的长度为1或0，直接返回
41    }
42    int mid = (left + right) / 2; // 找到中点，将数组分成两半
43    merge_sort(a, left, mid); // 递归排序左半部分
44    merge_sort(a, mid + 1, right); // 递归排序右半部分
45    merge(a, left, mid, right); // 合并两个有序的半部分
46}
47
48int main() {
49        int n = 0;
50        cin >> n;
51        for (int i = 0; i < n; i++) {
52                cin >> a[i];
53        }
54        merge_sort(a, 0, n - 1);
55        for (int i = 0; i < n; i++) {
56                cout << a[i] << ' ';
57        }
58        cout << endl;
59        return 0;
60}