参考了: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;
}