题目传送门<==戳这
这道题考查对 插入（选择）排序 和 归并排序 “原理” 的掌握程度，如果只是背的模板，那这道题可能会超时或没思路。
原始序列==> a ,
某排序算法产生的中间序列==> b
关键点：
1.判断排序类型：
遍历b数组，第一次 b [ i ] > b [ i + 1 ] 的时候就是下一次插入排序的标志性位置；
然后对从 i+1 开始遍历，如果 a [ i ] == b [ i ] 直到最后都成立，说明是插入排序，反之为归并排序；
2.插入排序的下一个排序：
即加入后面一个元素进行排序
puts("Insertion Sort");sort(b+1,b+1+id); ==>id是第一次 b [ i ] > b [ i + 1 ] 的时候 i+1 的值printf("%d",b[1]);for(int i=2;i<=n;i++) printf(" %d",b[i]);这里暂时没看懂也没关系，后面看整体更清晰
3.归并排序的下一个排序
让 a 数组（即原序列数组）每次循环都模拟归并排序，再与 b 数组匹配puts("Merge Sort");int k=1; ==>k是归并排序的“规模”while(1){
int i;for(i=1;i<=n;i++){
==>匹配过程，如果二者不完全相同，继续归并排序if(a[i]!=b[i]){
break;}}k*=2; ==>调整“规模”int j;for(j=0;j<n/k;j++){
==>仔细琢磨一下，归并排序的分块排序思想sort(a+1+j*k,a+1+(j+1)*k);}sort(a+1+j*k,a+1+n); ==>因为元素个数不一定是“规模”的整数倍，所以要对“尾巴”进行单独处理if(i==n+1){
==>如果两数组完全相同，则跳出循环break; ==>这里特别注意这个判断并不是在排序代码的前面==>因为是求下一个排序，所以制造完下一个排序后才跳出循环，仔细琢磨}}printf("%d",a[1]);for(int i=2;i<=n;i++){
printf(" %d",a[i]);}
上完整代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=200;
int a[maxn],b[maxn];
int main(){
int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) scanf("%d",&b[i]);int sign=1,id;==>判断排序类型int i;for(i=1;i<n;i++){
if(b[i]>b[i+1]){
id=i+1;break;}}int j;for(j=i+1;j<=n;j++){
if(a[j]!=b[j]){
sign=0;}}==>sign==1为插入排序if(sign==1){
puts("Insertion Sort");sort(b+1,b+1+id);printf("%d",b[1]);for(int i=2;i<=n;i++) printf(" %d",b[i]);}else{
puts("Merge Sort");int k=1;while(1){
int i;for(i=1;i<=n;i++){
if(a[i]!=b[i]){
break;}}k*=2;int j;for(j=0;j<n/k;j++){
sort(a+1+j*k,a+1+(j+1)*k);}sort(a+1+j*k,a+1+n);if(i==n+1){
break;}}printf("%d",a[1]);for(int i=2;i<=n;i++){
printf(" %d",a[i]);}}
}