判断是插入还是归并函数。题目所说“保证每组测试的结果是唯一的”，所以判断其中一个即可。而判断插入函数，由于插入排序必然使得
所以插入排序满足前面的元素有序，而后面的元素待排元素与原始序列相等。所以由以下代码来判断。
a[j] == b[j]
if(j == n)
当后面待排元素和原始序列都满足相等的条件，那么就可以用 j == n 来判断为插入排序。
sort(a, a + i + 2);
当时想了半天为什么这里要+2。对于插入排序来说，再迭代一轮就将已排序末尾的后一个未排序元素拉进来。而前面由
for (i = 0; i < n - 1 && b[i] <= b[i + 1]; i++);
给出了已排序元素的下标位置。但是下标 i 与后一个元素相差1。而 sort 是 sort (first, last) 对 [first, last) 范围内的元素进行排序范围内排序，不包括 last 所以要在下一个待排序元素的下标 i + 1 基础上再 + 1。
以前都是 (a, a + n) 直接 + n 的，忽略了这样用的真正原因是什么。
同时这里还学到，当有某些部分不理解的时候，需要将这部分里面的细节拆开理解。比如前面的 sort 里有一个 i，当时不理解这个 i 是干什么的。所以就用了 cout 将这个 i 及其它对应的元素打印出来。这才知道这个东西在这里具有什么意义。
int k = 1, flag = 1;
k 是每次归并排序时，组的元素的个数，初始化为 1每一次进入循环时会对组的个数加倍。加倍后再进行归并和排序。
k *= 2;
for(i = 0; i < n; i++)
if(a[i] != b[i])
flag = 1;
flag用来标记是否进行下一次循环，初始时设为1进入第一次循环，然后进入后初始化为 flag = 0，如果可以判断为当前序列已经与中间序列 b[] 相等，那么就不需要设 flag = 1，即不再进行下一次循环。本循环再排序迭代一次即结束。
for(i = 0; i < n / k; i++)
sort(a + i * k, a + (i + 1) * k);
sort(a + n / k * k, a + n);
这代码里面出现两次 n / k ，而因为 n 和 k 都是整数所以 n / k 的结果会向下取正。比如 n = 10，k = 3时，n / k = 3。
如果当最后一个组非 k 倍数时，比如上面的情况，那么 for 循环会对前面整的组进行归并和排序，而留下最后一个组单独 sort 排序。
而单独 sort 排序的话同样有 n / k 并且还 * k，但同样因为整型除法的向下取正，所以这里的结果就是最后的组的首元素位置 n / k * k = 9。
当最后一个组为 k 倍数时，比如 n = 9， k = 3。那么 for 循环刚好把三个组排序，而单独的 sort 因为 n / k * k = 9， n = 9，所以只是对单一元素处理，不会导致其他的结果。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, a[100], b[100], i, j;
cin >> n;
for(i = 0; i < n; i++)
cin >> a[i];
for(i = 0; i < n; i++)
cin >> b[i];
// 判断是否是插入排序
for(i = 0; i < n && b[i] <= b[i+1]; i++);
for(j = i + 1; j < n && a[j] == b[j]; j++);
if(j == n){
cout << "Insertion Sort" << endl;
sort(a, a + i + 2);
}
else{
cout << "Merge Sort" << endl;
int k = 1, flag = 1;
while(flag){
flag = 0;
for(i = 0; i < n; i++)
if(a[i] != b[i])
flag = 1;
k *= 2;
for(i = 0; i < n / k; i++)
sort(a + i * k, a + (i + 1) * k);
sort(a + n / k * k, a + n);
}
}
for(i = 0; i < n; i++)
cout << (i ? " " : "") << a[i];
}