传送门

思路

每次从中间，将数组分为左半边和右半边，然后递归该过程（从上往下的过程）
归并相当于从下往上合并的过程（这个过程相当于合并两个递增序列 – 双指针算法）

#include<iostream>
using namespace std;
const int N = 1e5 + 100;
int n;
int f[N];
int tmp[N];

void merge_sort(int f[], int l, int r)
{
    if(l >= r) return;
    int mid = l + r >> 1;
    merge_sort(f, l, mid), merge_sort(f, mid + 1, r);

    //下面是合并过程， 相当于合并两个有序链表过程 ==双指针算法。
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
        if(f[i] <= f[j]) tmp[k ++] = f[i ++];
        else tmp[k ++] = f[j ++];

    while(i <= mid) tmp[k ++] = f[i ++];
    while(j <= r) tmp[k ++] = f[j ++];

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

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

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