Contents

1. 1. 输入格式：
2. 2. 输出格式：
3. 3. 输入样例 1：
4. 4. 输出样例 1：
5. 5. 输入样例 2：
6. 6. 输出样例 2：
7. 7. 分析：
8. 8. 代码：

根据维基百科的定义：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

输入格式：

输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。

输出格式：

首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。

输入样例 1：

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

输出样例 1：

Insertion Sort
1 2 3 5 7 8 9 4 6 0

输入样例 2：

10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

输出样例 2：

Merge Sort
1 2 3 8 4 5 7 9 0 6

分析：

如果是插入排序，b[0]b[i]有序，其后对于j∈[i+1,n-1]都有a[j]==b[i]。代码中i下标用来记录最后一个排好序的下标，j用用来检验是否是插入排序。如果是插入排序，j会循环到 a[n-1] == b[n-1]，即循环完成 j == n-1 。对于插入排序，下一步序列排序a[0]a[i+1]即可，sort(a,a+i+2)。对于归并排序，通过循环模拟排序过程，flag检验排序中间结果是否和b数组相同。

代码：

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n,a[110],b[110],i,j,k=1;
    cin >> n;
    for (i=0;i<n;i++)
        cin >> a[i];
    for (i=0;i<n;i++)
        cin >> b[i];

    for (i=0;i<n-1 && b[i] <= b[i+1];i++);
    for (j=i+1;j<n && a[j] == b[j];j++);

    if (j == n){
        sort(a,a+i+2);
        cout << "Insertion Sort" << endl;
    }
    else {
        cout << "Merge Sort" << endl;
        bool flag=true;
        while (flag){
            flag = false;
            k*=2;
            for (i=0;i<n;i++)
                if (a[i] != b[i])
                    flag = true;
            for (i=0;i<n/k;i++)
                sort(a+i*k,a+(i+1)*k);
            sort(a+n/k*k,a+n);
        }
    }
    cout << a[0];
    for (i=1;i<n;i++)
        cout << " "<<a[i];
    return 0;
}