题目描述

在归并排序中添加几个输出就可以快速了解模板思路；

#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+10;
int n;
int q[N];// tmp[N];

void merge_sort(int q[], int l, int r)
{
    int tmp[N] = {0};
    if(l>=r) return;
    int mid = (l + r) >> 1;
    merge_sort(q, l, mid), merge_sort(q, mid+1, r);
    int k = 0, i=l, j= mid+1;
    while(i <= mid && j <=r)
    {
        if(q[i] <= q[j]) tmp[k ++] = q[i ++];
        else tmp[k++] = q[j++];
    }

    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k ++] = q[j ++];
    cout << "mid = " << mid <<  "，l = "<< l << "，r = "<< r << "时，tmp 里的值为："<< endl;
    for(int i=0; i<n; i++) cout << tmp[i] << ' ';
    putchar('\n');
    for(i = l, j=0; i<=r; i++, j++) q[i] = tmp[j];
    cout << "mid = " << mid << "时，q[i] 里的值为：" << endl;
    for(int i=0; i<n; i++) cout << q[i] << ' ';
    putchar('\n');

}

int main()
{
    scanf("%d", &n);
    for(int i=0;i<n;i++) scanf("%d", &q[i]);
    int l=0, r = n-1;
    merge_sort(q, l, r);
    for(int i=0; i<n; i++) cout << q[i] <<' ';
}