参考了:https://www.acwing.com/activity/content/code/content/323536/ 和 https://www.acwing.com/activity/content/code/content/272766/

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N = 110;
int a[N], b[N];
int n =0;

bool check()
{
    for(int i = 1; i <=n; ++i)
        if(a[i] != b[i])
            return false;
    return true;
}


int main()
{
    cin >> n;
    for(int i=1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <=n; ++i) cin >> b[i];

    int p=2;
    while(p <=n && b[p] >= b[p-1]) ++p;

    int pos = p;
    while(p<= n && a[p] == b[p]) ++p;

    if(p == n+1) //插入排序
    {
        puts("Insertion Sort");
        p = pos;
        while(p>1 && b[p]<  b[p-1])
            swap(b[p],b[p-1]),--p;
        for(int i=1; i<=n; ++i)
        {
            cout << b[i];
            if(i < n)
                cout << ' ';
        }
    }
    else //归并排序
    {
        puts("Merge Sort");

        int k = 1;
        while(true)
        {
            bool match = check();
            int len = 1 << k;
            for(int i = 1; i <= n; i+=len)
            {
                sort(a+i,a+min(n+1,i+len));
            }
            if(match)
                break;
            ++k;
        }

        for(int i=1; i<=n; ++i)
        {
            cout << a[i];
            if(i < n)
                cout << ' ';
        }
    }

    return 0;
}