问题 N: 案例7-1.2 插入排序还是归并排序

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:519 解决:238

题目描述

根据维基百科的定义:

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

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

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

输入

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

输出

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

样例输入 复制

4
3 4 2 1
3 4 2 1

样例输出 复制

Insertion Sort
2 3 4 1

来源/分类