注意该图和代码有点不符，按照代码中mid的算法，mid=(0+2)>>1=1，故左区间为[0, 1]，右区间为[2, 2]，故6 9 4应该划分为6 9和4，但原理都一样的。

这里采用打印的方式看算法的执行流程，也可直接debug看。

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int num = 1, n, a[N], tmp[N];

void merge_sort(int q[], int l, int r)
{
    if (l >= r)
    {
//        cout << endl << "【第" << num++ << "轮递归】" << endl;
        return;
    }

    int mid = (l + r) >> 1;

    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int i = l, j = mid + 1, m = 0;
    cout << endl << "此时排序的区间[l, r]为：[" << l << ", " << r << "]" <<endl;
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j]) tmp[m++] = q[i++];
        else tmp[m++] = q[j++];
    }
    while (i <= mid) tmp[m++] = q[i++];
    while (j <= r) tmp[m++] = q[j++];

    for (i = l, j = 0; i <= r; i++, j++)
    {
        cout << "tmp[j=" << j << "]=" << tmp[j] << ", ";
    }
    cout << endl;
    for (i = l, j = 0; i <= r; i++, j++)
    {
        q[i] = tmp[j];
        cout << "q[i=" << i << "]=" << q[i] << ", ";
    }

}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    merge_sort(a, 0, n - 1);

    for (int i = 0; i < n; i++) cout << a[i] << ' ';

    return 0;
}