7-2 二路归并排序 分数 15 作者 黄龙军 单位 绍兴文理学院 给定一个整数序列，请按非递减序输出采用二路归并排序（递归法）的各趟排序后的结果（每完成一次归并操作就输出归并后的结果）。 输入格式: 测试数据有多组，处理到文件尾。每组测试数据第一行输入一个整数n（1≤n≤100），第二行输入n个整数。 输出格式: 对于每组测试，输出若干行，每行是一趟排序后的结果，每行的每两个数据之间留一个空格。 输入样例: 6 73 12 27 98 81 64 输出样例: 12 73 27 98 81 64 12 27 73 98 81 64 12 27 73 81 98 64 12 27 73 64 81 98 12 27 64 73 81 98

以下是该问题的一个可能解法：

#include <iostream>
using namespace std;

const int N = 110;

int n;
int a[N], b[N];

void merge_sort(int l, int r)
{
    if (l == r) return;
    int mid = (l + r) / 2;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        if (a[i] <= a[j]) b[k++] = a[i++];
        else b[k++] = a[j++];
    while (i <= mid) b[k++] = a[i++];
    while (j <= r) b[k++] = a[j++];
    for (int i = 0; i < k; i++) a[l + i] = b[i];
    for (int i = l; i <= r; i++) cout << a[i] << " ";
    cout << endl;
}

int main()
{
    while (cin >> n)
    {
        for (int i = 0; i < n; i++) cin >> a[i];
        merge_sort(0, n - 1);
    }
    return 0;
}

该算法的时间复杂度为 $O(n\log n)$，其中 $n$ 是序列的长度。首先将序列分成两部分，然后对每部分递归地进行排序，最后将两部分合并成一个有序序列。每次合并时，需要比较两部分的元素大小，并按顺序合并。在合并的过程中，需要辅助数组 $b$ 来存储合并的结果。每完成一次归并操作，就输出归并后的结果。