题意：
输入一个正整数N（<=100），接着输入两行N个整数，第一行表示初始序列，第二行表示经过一定程度的排序后的序列。输出这个序列是由插入排序或者归并排序得到的，并且下一行输出经过再一次排序操作所得到的序列。数据保证了不会有两种排序方式都可以得到的序列。
代码：
#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int a[107];
int b[107];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i];
for(int i=1;i<=n;++i)
cin>>b[i];
int pos=0;
for(int i=n;i;--i)
if(a[i]!=b[i]){
pos=i;
break;
}
int flag=1;
int loc=0;
for(int i=1;i<n;++i)
if(b[i]>b[i+1]){
loc=i;
break;
}
for(int i=loc+1;i<=n;++i)
if(a[i]!=b[i]){
flag=0;
}
if(flag){
cout<<"Insertion Sort\n";
sort(a+1,a+1+loc+1);
for(int i=1;i<=n;++i){
cout<<a[i];
if(i<n)
cout<<" ";
}
}
else{
cout<<"Merge Sort\n";
int t=1;
while(1){
int flag=0;
for(int i=1;i<=n;++i)
if(a[i]!=b[i]){
flag=1;
break;
}
t*=2;
for(int i=1;i<=n/t;++i)
sort(a+(i-1)*t+1,a+i*t+1);
sort(a+n/t*t+1,a+n+1);
if(!flag)
break;
}
for(int i=1;i<=n;++i){
cout<<a[i];
if(i<n)
cout<<" ";
}
}
return 0;
}
【PAT甲级】1089 Insert or Merge (25 分)（插入排序和归并排序）
原文：https://www.cnblogs.com/ldudxy/p/11901958.html