根据维基百科的定义：
插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作：首先将原始序列看成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
考察插入排序与归并排序，需注意的是，此处考察的是归并排序的自底向上的方法而非递归形式的自顶向下。
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<ctype.h> 5 #include<math.h> 6 //交换元素 7 void swap(int &a,int &b){ 8 int temp = a; 9 a = b; 10 b = temp; 11 } 12 //打印数组 13 void print(int a[],int n){ 14 printf("%d",a[0]); 15 for(int i=1;i<n;i++){ 16 printf(" %d",a[i]); 17 } 18 printf(" "); 19 } 20 21 //归并排序中的合并操作 22 void merge(int a[],int start,int mid,int end){ 23 int c[200]; 24 int start1 = mid+1; 25 int k = 0; 26 int h = start; 27 while(start<=mid&&start1<=end){ 28 if(a[start]<a[start1]) 29 c[k++] = a[start++]; 30 else 31 c[k++] = a[start1++]; 32 } 33 while(start<=mid) 34 c[k++] = a[start++]; 35 while(start1<=end) 36 c[k++] = a[start1++]; 37 for(int i=0;i<k;i++) 38 a[i+h] = c[i]; 39 40 } 41 //归并排序中自顶向下的递归形式 42 /*void mergeSort(int a[],int start,int end){ 43 if(start<end){ 44 int mid = (start+end)/2; 45 mergeSort(a,start,mid); 46 mergeSort(a,mid+1,end); 47 merge(a,start,mid,end); 48 print(a,10); 49 } 50 }*/ 51 52 //归并排序中自底向下的形式 53 void mergeSort(int a[],int length,int n){ 54 int i; 55 for(i=0;i+2*length-1<n;i=i+length*2) 56 merge(a,i,i+length-1,i+2*length-1); 57 if(i+length-1<n) 58 merge(a,i,i+length-1,n); 59 } 60 61 int main(){ 62 int n; 63 int a[200]; 64 int a1[200]; 65 int b[200]; 66 int j; 67 int flag=0,flag1=0; 68 scanf("%d",&n); 69 for(int i=0;i<n;i++){ 70 scanf("%d",&a[i]); 71 a1[i] = a[i]; 72 } 73 for(int i=0;i<n;i++){ 74 scanf("%d",&b[i]); 75 } 76 //插入排序 77 for(int i=1;i<n;i++){ 78 for(j=i;j>0;j--){ 79 if(a[j]<a[j-1]){ 80 swap(a[j],a[j-1]); 81 } 82 } 83 if(flag){ 84 printf("Insertion Sort "); 85 print(a,n); 86 return 0; 87 } 88 for(j=0;j<n;j++){ 89 if(a[j]!=b[j]){ 90 break; 91 } 92 } 93 if(j==n){ 94 flag = 1; 95 } 96 } 97 //归并排序 98 int length; 99 for(length=1;length<n;length=length*2){ 100 mergeSort(a1,length,n-1); 101 if(flag1){ 102 printf("Merge Sort "); 103 print(a1,n); 104 return 0; 105 } 106 for(j=0;j<n;j++){ 107 if(a1[j]!=b[j]) 108 break; 109 } 110 if(j==n) 111 flag1 = 1; 112 } 113 114 115 116 }