解题思路： 本题需要对插入排序和归并排序有一定的了解。
对于插入排序，可将序列看做前后两个组成部分，前部分一定是有序的，后部分保持原数组元素不变；
本题涉及的归并排序并非实际算法的归并排序算法。真正的归并排序是“先左后右，分而治之” 的，而并非本题从头到尾一组一组的排。笔者一开始就天真的以为直接敲出来归并算法，然后加上判读就可以了。然而还是naive了。
本题所的归并过程是这样的： 对于任意一串数组，一分为二，而分为四……直到每一组只剩下两个元素，将该组的两个元素进行排序，然后再将与它相邻的另外两个元素的一组排序，将这两组归并到一起，成为含有四个元素的一组，同理，另外其他相邻两组均可以形成四个元素为一组的有序组，将这四个元素为一组的数组合并为八个元素的数组。如此循环下去，直到最后形成一个数组，此时该数组就是原数组的有序序列了。 具体请看下方的栗子：
任意数组 3 1 2 8 7 5 9 4 一分为二 (3 1 2 8) ( 7 5 9 4) 二分为四 (3 1) (2 8) (7 5) (9 4) 将每组排序 (1 3) (2 8) (5 7) (4 9) 四合为二 (1 2 3 8) (4 5 7 9) 二合为一 1 2 3 4 5 7 8 9具体步骤如下：
插入排序： 创建一个i指针，记录下最大有序串的末尾角标。再创建一个j指针接力，初始化为前面的最大角标，若j指针之后的元素与原数组相同则为插入排序。然后将原数组的前n+2位（因为n+1是有序串的最后一位，在这里不好解释，具体看代码）进行排序即可求得答案。
归并排序： 设置步长k为2，将每个步长内的元素进行排序，执行【长度/步长】次，因为数据个数不一定为偶数，所以需要对额外剩余的元素进行排序。执行完上述步骤后，步长扩大2倍，重复执行上述操作，直到找到与题目所给的中间序列符合的一次，此时在此基础上再执行一次即为最后结果。
示例代码：
#include<iostream> #include<algorithm> #include<vector> using namespace std; int main() { int len; cin >> len; vector<int> arr(len);//原数组 vector<int> test(len);//中间序列 for (int i = 0; i < len; i++) { int temp; cin >> temp; arr[i] = temp; } for (int i = 0; i < len; i++) { int temp; cin >> temp; test[i] = temp; } bool flag = false;//true 为插入排序，否则为归并排序 int i,j; for (i = 0; i < len-1 && test[i] <= test[i+1]; i++);//前部都是有序的吗？ for (j = i + 1; j < len && arr[j] == test[j]; j++);//后部分都是原数组的数据吗？ if (j == len) { flag = true; int m = i + 2; sort(arr.begin(), arr.begin() + m); cout << "Insertion Sort" << endl; } if (!flag) { bool goon = true; int k = 2;//步长 while (1) { int time = len / k; //执行次数,向下取整 vector<int>::iterator start = arr.begin(); for (int i = 0; i < time; i++) { sort(start,start+k); start += k; } //继续排剩下的部分 if (start < arr.end()) { sort(start, arr.end()); } if (!goon) break;//在这里判断，保证多执行一次 k *= 2;//步长加倍 for (int i = 0; i < len && arr[i] == test[i]; i++) {//检查是否与给出的中间序列相等 if (i == len-1) goon = false; } } cout << "Merge Sort" << endl; } for (int i = 0; i < len - 1; i++) { cout << arr[i] << " "; } cout << arr[len - 1]; return 0; }