时间复杂度：n * log(n)
思想：
一、找到数组的重点，依次把他分成两部分，记录下来，
二、将左边和右边都用递归排序，排好顺序，只要用了merge_sort，就说明这个范围就已经排好序了
三、归并排序，合二为一。这两个数组的元素两两比较，然后不断把最小的数放在数组中

#include<bits/stdc++.h>

using namespace std;
//存放录入的数据
int p[1000010];
//存放每一个区间排好序的数据
int result[1000010];
void merge_sort(int p[], int l, int r) {
    //先判断一下，如果就是这个范围已经递归到只剩一个元素了，那肯定就不用排序了，就直接return
    if (l >= r) {
        return ;
    }
    //然后找到最中间值的坐标，分成两部分
    int mid = l + r >> 1;
    //用一下归并排序，将以mid分开的两个区间排好序
    merge_sort(p, l, mid);
    merge_sort(p, mid + 1, r);
    int k = 0;
    //然后将这两个区间合并成一个区间，这就是归并排序的核心操作
    int i = l;//第一个区间的开头
    int j = mid + 1;//第二个元素的开头
    //每次从区间的第一个数取出来，然后比较，合并成同一个区间
    while (i <= mid && j <= r) {
        //开始归并排序的核心：在已经排好序的两个数组中不断寻找最小值，然后放入结果数组中，直至其中一个数组存放完毕，然后把没有存完的另一个数组的剩余元素存放进去
        if (p[i] <= p[j]) {
            result[k ++] = p[i ++];
        } else {
            result[k ++] = p[j ++];
        }
    }
    //把数组中没放进去的放进去
    //由于不知道是哪个没放进去就两个都判断一下
    while (i <= mid) {
        result[k ++] = p[i ++];
    }
    while (j <= r) {
        result[k ++] = p[j ++];
    }
    //再把结果放回数组中，这一步是必须有的，因为排序是一个递归的过程，有这一步才能将每一步操作更新到p数组中，要不然递归毫无作用
    for (int i = l, j = 0; i <= r; i ++, j ++) {
        p[i] = result[j];
    }
}
int main () {
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> p[i];
    }
    merge_sort(p, 0, n - 1);
    for (int i = 0; i < n; i ++) {
        cout << p[i] << ' ';
    }
    return 0;
}