1035 插入与归并（测试点6）

solution

• 类型判断：插入排序中已排序的部分有序，未排序的和原数组元素相同；否则为归并排序
• 测试点6：对于归并排序的子序列长度，不能简单视为前k个有序则子序列长度就是k
  例如该测试用例的归并排序的子序列长度应该为2，而非4

8
2 1 3 8 5 2 4 6
1 2 3 8 2 5 4 6

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 110;
int pre[maxn], did[maxn];
int main(){int n, cnt = 0, flag = 0, p, t;scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d", pre + i);}for(int i = 0; i < n; i++){scanf("%d", did + i);}for(p = 0; p < n; p++){if(p == 0) t = did[p];if(did[p] < t) break;t = did[p];cnt++;}for(; p < n; p++){if(did[p] != pre[p]){flag = 1;break;}}if(flag){printf("Merge Sort\n");t = 1;while(t){t = 0;for(int i = 0; i < n / cnt; i++){for(int j = i * cnt; j < (i + 1) * cnt - 1; j++){if(did[j] > did[j + 1]) t = 1;}}if(t) cnt /= 2;}cnt *= 2;for(int i = 0; i < n / cnt; i++){sort(did + i * cnt, did + (i + 1) * cnt);}sort(did + n / cnt * cnt, did + n);}else{printf("Insertion Sort\n");sort(did, did + cnt + 1);}for(int i = 0; i < n; i++){if(i) printf(" ");printf("%d", did[i]);}return 0;
}