include <iostream>

/* run this program using the console pauser or add your own getch, system("pause") or input loop
题意：
1、判断是归并还是插入
2、输出算法名字+下一次迭代的算法

解题：
1、模拟归并和插入的每一步过程
2、先进行插入排序，如果执行过程中发现与给定序列吻合，则说明是插入，并计算下一步
如果不是，则用归并，如果过程中序列吻合，则计算下一步

learn && wrong:
1、数据范围小，归并可以不写合并函数，直接用sort函数
2、陷阱：初试序列不参与是否与目标序列相同的比较，（也就是题目中的中间序列是不包括初试序列的）不考虑这个会导致某个数据产生双解
3、忘记插入排序怎么写，忘记归并迭代怎么写
4、有一个issame函数，和一个show函数，+
insertsort函数，改变在进入循环开始，就判断，之后的时候，还进行一次迭代，再判断，如果成立返回true，与主函数里的if形成一套并调用show函数
mergesort函数，也是一开始判断，中间再迭代一次，与之不同的是，最后判断的时候，直接输出而不是在else这个模块输出了
5、mergesort函数与sort函数连用，其实迭代的写法也不难记忆，就是没经常写
*/

include <algorithm>

using namespace std;
const int N = 111;
int origin[N], tempori[N], changed[N];
int n;//元素个数

bool issame(int a[], int b[]) {
for (int i = 0;i < n;++i) {
if (a[i] != b[i]) return false;
}
return true;
}

void showarray(int a[]) { //输出数组
for (int i = 0;i < n;++i) {
cout << a[i];
if (i != n - 1) cout << " ";
}
cout << endl;
}

bool insertsort() {//插入排序
bool flag = false; //记录是否存在数组中间步骤与changed数组相同
for (int i = 1;i < n;++i) {
if (i != 1 && issame(tempori, changed)) {
flag = true; //中间步骤与目标相同，且不是初试序列
}

    //以下为插入部分
    int temp = tempori[i], j = i;
    while (j > 0 && temp < tempori[j - 1]) {
        tempori[j] = tempori[j - 1];
        --j;
    }
    tempori[j] = temp;

    if (flag == true) {
        return true;
    }
}
return false;

}

void mergesort() {
bool flag = false; //记录是否存在数组中间步骤与changed相同
for (int step = 2;step / 2 <= n;step *= 2) {

    if (step != 2 && issame(tempori,changed) == true) { //中间步骤与目标序列相同，且不是初试序列 
        flag = true;
    }

    for (int i = 0;i < n;i += step) {
        sort(tempori + i, tempori + min(step + i, n));
    }

    if (flag == true) {
        showarray(tempori);
        return;
    }
}

}

int main(int argc, char** argv) {
cin >> n;
for (int i = 0;i < n;++i) {
cin >> origin[i];
tempori[i] = origin[i]; //数组备份
}

for (int i = 0;i < n;++i) {
    cin >> changed[i];      //目标数组
}

if (insertsort()) {
    printf("Insertion Sort\n");
    showarray(tempori);
}
else {
    printf("Merge Sort\n");
    for (int i = 0;i < n;++i) {
        tempori[i] = origin[i];
    }
    mergesort();
}
return 0;

}