#include <iostream>
#include <algorithm>
using namespace std;
int a[105],b[105],N;
int firstDifferent=N-1;
bool InsertSort()
{
for(int i=0;i<N-1;i++)
{
if(b[i+1]<b[i])
{
firstDifferent=i+1;
break;
}
}
for(int i=firstDifferent;i<N;i++)
if(a[i]!=b[i])
return false;
return true;
}
int main()
{
cin>>N;
for(int i=0;i<N;i++)
cin>>a[i];
for(int i=0;i<N;i++)
cin>>b[i];
if(InsertSort()==true)
{
sort(b,b+firstDifferent+1);
cout<<"Insertion Sort"<<endl;
for(int i=0;i<N;i++)
{
if(i==0)
cout<<b[i];
else
cout<<" "<<b[i];
}
}
else
{
int start=0,end=1,gap=1,find=0;
while(1)
{
gap*=2;
for(int i=0;i*gap<N;i++)
{
start=i*gap;
end=i*gap+gap<N?i*gap+gap:N;
sort(a+start,a+end);
}
if(find==1)
{
cout<<"Merge Sort"<<endl;
for(int i=0;i<N;i++)
{
if(i==0)
cout<<a[i];
else
cout<<" "<<a[i];
}
break;
}
int index=0;
while(index<N)
{
if(a[index]!=b[index])
break;
index++;
}
if(index==N)
find=1;
}
}
return 0;
}
本题考查插入排序和归并排序。
判断是否为插入排序的思路很简单，不需要模拟插入排序的整个过程，因为插入排序的[0，k]元素一定是升序的，[k+1,N-1]的元素一定是和原序列相同的。
判断是否为归并排序就需要 模拟归并排序的过程，gap为当前的步长，就是一个子序列的长度。
