给定一个整数序列，请按非递减序输出采用二路归并排序（递归法）的各趟排序后的结果（每完成一次归并操作就输出归并后的结果）。

二路归并排序是一种基于分治思想的排序算法，它将待排序序列分成两个子序列，分别进行排序，然后将两个有序子序列合并成一个有序序列。在递归过程中，每一次归并操作都会输出归并后的结果，最终得到非递减序列。

具体实现过程如下：

1. 将待排序序列分成两个子序列，分别进行排序。

2. 对两个有序子序列进行归并操作，得到一个更大的有序序列。

3. 重复步骤1和2，直到所有子序列都被排序并合并成一个有序序列。

以下是一个示例：

给定序列：[5, 3, 8, 6, 4, 2, 7, 1]

第一趟排序：[3, 5] [6, 8] [2, 4] [1, 7]

第二趟排序：[3, 5, 6, 8] [1, 2, 4, 7]

第三趟排序：[1, 2, 3, 4, 5, 6, 7, 8]

最终输出的非递减序列为：[1, 2, 3, 4, 5, 6, 7, 8]

相关问题

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$ 来存储合并的结果。每完成一次归并操作，就输出归并后的结果。