根据维基百科的定义：
插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作：首先将原始序列看成 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
难点在于判断归并函数到底执行到了哪一步 有两种思路，第一是模拟，第二是根据充要条件判断。 在判断语句
for (L = 2; L <= N; L *= 2) { for (j = L; j < N; j += (2 * L)) if(b[j - 1] > b[j]) break; if (j < N) break; }
中，首先，L是从2开始的，因为题目提到了“中间序列”，所以必然是执行了一步以上 然后，j需要跨越两个L去判断是否符合，因为两个L中间的部分，必然在前一次归并中排序好了 跳出循环以后，j>=N的情况，说明在数组内部是符合的，所以继续循环，如果不符合，说明第L步归并还没有做，因此，执行第L步归并 最后，还需要对last two sections和last one section 的情况进行判断
#include<iostream> #include<queue> #include<cstdlib> #include<cstdio> #include<cstring> using namespace std; int IsInsertion(int* a, int* b, int N) { int i, k; for (i = 1; i < N; i++) if (b[i] < b[i - 1]) break; k = i; for (; i < N; i++) if (b[i] != a[i]) break; if (i == N) return k; else return 0; } void NextInsertion(int* b, int N, int k) { int i, tmp; cout << "Insertion Sort" << endl; tmp = b[k]; //move right all elements that bigger than insert position for (i = k - 1; i >= 0; i--) if (b[i] > tmp) b[i + 1] = b[i]; else break; b[i + 1] = tmp; cout << b[0]; for (i = 1; i < N; i++) cout << " " << b[i]; } void NextMerge(int* b, int N) {//pay attention to the length of moment merge section cout << "Merge Sort" << endl; int i, p1, p2, p, L,j; int* tmp; tmp = (int*)malloc(sizeof(int) * N); for (L = 2; L <= N; L *= 2) { for (j = L; j < N; j += (2 * L)) if (b[j - 1] > b[j]) break; if (j < N) break; } //iteration p = 0; for (i = 0; i < (N - L - L); i += (2 * L)) { p1 = i; p2 = L + i; while ((p1 < (L + i)) && p2 < (2 * L + i)) { if ((b[p1] > b[p2])) tmp[p++] = b[p2++]; else tmp[p++] = b[p1++]; } while (p1 < (i + L)) tmp[p++] = b[p1++]; while (p2 < (i + 2 * L)) tmp[p++] = b[p2++]; } if ((N - i) > L) {//last two sections p1 = i; p2 = i + L; while ((p1 < (i + L)) && (p2 < N)) { if ((b[p1] > b[p2])) tmp[p++] = b[p2++]; else tmp[p++] = b[p1++]; } while (p1 < (i + L)) tmp[p++] = b[p1++]; while (p2 < N) tmp[p++] = b[p2++]; } else//last one section while (i < N) tmp[i] = b[i++]; cout << tmp[0]; for (i = 1; i < N; i++) cout << " " << tmp[i]; } int main() { int N, i, k; int* a, * b; cin >> N; a = (int*)malloc(sizeof(int) * N); b = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; i++) scanf("%d", &a[i]); for (int i = 0; i < N; i++) scanf("%d", &b[i]); if (k = IsInsertion(a, b, N)) NextInsertion(b, N, k); else NextMerge(b, N); return 0; }