根据维基百科的定义：
插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。
现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？
输入格式：
输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。
输出格式：
首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。
输入样例 1：
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
输出样例 1：
Insertion Sort
1 2 3 5 7 8 9 4 6 0
输入样例 2：
10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6
输出样例 2：
Merge Sort
1 2 3 8 4 5 7 9 0 6
思路：根据定义，插入排序是每一步对一个元素进行排序，由此我们可以用STL的sort对原始序列模拟出每一步插入排序，同时跟所给出的中间序列进行比较，可以自己写个函数或者用equal（）函数比较，如果找到中间序列，那么就是插入排序，再进行一轮插入排序输出即可，但是如果最后还是没有找到中间序列，那么就是归并排序，注意这里有个坑点就是要重新对原始序列进行归并排序的模拟，否则如果对中间序列模拟归并排序的下一步会错一个点......
1 #include<iostream>
2 #include<cstring>
3 #include<cmath>
4 #include<cstdio>
5 #include<algorithm>
6 #include<map>
7 #include<set>
8 #include<vector>
9 using namespace std;
10 #define ll long long
11 #define inf 99999999
12 int n;
13 bool compare(int start[],int mid[])
14 {
15 int flag=0;
16 for(int i=0;i<n;i++)
17 {
18 if(start[i]!=mid[i])
19 {
20 flag=1;
21 break;
22 }
23 }
24 if(flag==1)
25 return false;
26 else
27 return true;
28 }
29 int main()
30 {
31 scanf("%d",&n);
32 int start[101];//原始序列
33 int start1[101];//保存原始序列
34 int mid[101];//中间序列
35 for(int i=0;i<n;i++)
36 {
37 scanf("%d",&start[i]);
38 start1[i]=start[i];
39 }
40 for(int i=0;i<n;i++)
41 scanf("%d",&mid[i]);
42
43 int flag=0;//记录是否为插入排序
44 for(int i=1;i<n;i++)
45 {
46 sort(start,start+i+1);//进行一轮插入排序
47 //第一轮插入排序是排前两个数，等i轮插入排序则是排前i+1个数
48 if(compare(start,mid)==true)
49 {
50 flag=1;
51 sort(start,start+i+2);//进行下一轮插入排序
52 break;
53 }
54 }
55 if(flag)//为插入排序
56 {
57 printf("Insertion Sort
");
58 for(int i=0;i<n;i++)
59 i==n-1?printf("%d
",start[i]):printf("%d ",start[i]);
60 return 0;
61 }
62 flag=0;
63 for(int k=2;k<=n;k*=2)
64 {
65 int count=n/k;
66 for(int i=0;i<count;i++)
67 sort(start1+i*k,start1+(i+1)*k); //模拟归并排序
68 sort(start1+count*k,start1+n); //注意剩余部分也要排序
69 if(flag==1)//输出已经归并排序一步的序列
70 {
71 for(int i=0;i<n;i++)
72 i==n-1?printf("%d
",start1[i]):printf("%d ",start1[i]);
73 return 0;
74 }
75 if(compare(start1,mid)==true)//找到中间序列，判断为归并排序，刷新flag
76 {
77 printf("Merge Sort
");
78 flag=1;
79 }
80 }
81 return 0;
82 }