1035 插入与归并 （25 分）

根据维基百科的定义：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

输入格式：

输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。

输出格式：

首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。

输入样例 1：

103 1 2 8 7 5 9 4 6 01 2 3 7 8 5 9 4 6 0

输出样例 1：

Insertion Sort1 2 3 5 7 8 9 4 6 0

输入样例 2：

103 1 2 8 7 5 9 4 0 61 3 2 8 5 7 4 9 0 6

输出样例 2：

Merge Sort1 2 3 8 4 5 7 9 0 6

本题需熟练掌握insertion sort和merge sort，其中insertion sort需在每一次排序后检查当前数组的元素是否与待比较数组的元素相等，而merge sort需要在每一次归并后检查，所以merge sort 不能是递归版本，关于merge sort的非递归版本，我在另一博客有详细解释，链接如下：

https://blog.csdn.net/qq_37729102/article/details/81908746

Insertion sort的检查次数是n,merge sort的检查次数是log2n，这样，只要掌握两个sort的算法，那么一般可以通过此题。此题也可以使用C++STL的sort函数来模拟insertion sort和merge sort，其中sort函数在n规模小时是insertion sort，故直接拿来用即可。至于insertion sort模拟merge sort，首先需要知道merge sort的二路归并原理，即对两端k个元素归并，而使用sort，则是对一段k个元素排序，再对下一段k个元素排序，执行次数是n/k。

代码： 

手写sort版：

#include
        
         using namespace std;int *b=new int [100];//开头先定义临时数组，注意必须用new申请否则平台通不过 void Merge(int *elem,int lo,int mi,int hi){    //对elem数组的[lo,mi),[mi,hi)部分合并，注意右边是开区间     int lb=mi-lo;    int lc=hi-mi;    int *a=elem+lo;//a从elem的lo开始改变elem     int *c=elem+mi;//c从elem+mi开始到elem+hi的部分将与elem+lo到elem+mi作对比     for(int i=0;i
         
          0&&a[j-1]>t;j--)    a[j]=a[j-1];    a[j]=t;}bool Judge(int *a1,int *a2,int n){    for(int i=0;i
          
           >n;    for(int i=0;i
           
            >a1[i];        a3[i]=a1[i];    }    for(int i=0;i
            
             >a2[i];    int k=1;//定义步长，即合并元素个数    while(k
            
           
          
         
        

STL sort版：

#include
        
         #include
         
          using namespace std;void OutPut(int *a,int n){    for(int i=0;i
          
           >n;    for(i=0;i
           
            >a1[i];        a2[i]=a1[i];    }    for(i=0;i
            
             >a3[i];    for(i=2;i<=n;i++)//sort(a,a+n)指对a的n个元素排序，故n从2开始     {        sort(a1,a1+i);        if(equal(a1,a1+n,a3)&&i+1<=n)//使用equal函数将a1与a3作对比         {            cout<<"Insertion Sort\n";            sort(a1,a1+i+1);            OutPut(a1,n);            return 0;        }    }    for(k=2;k<=n;)    {        for(i=0;i