该题的归并排序是迭代形式的，不是递归形式的：

第一轮归并排序：划分为多个子序列，每个子序列包含 2个元素，然后合并每个子序列中的元素使每个子序列有序

第二轮归并排序：划分为多个子序列，每个子序列包含 4个元素，然后合并每个子序列中的元素使每个子序列有序

第三轮归并排序：划分为多个子序列，每个子序列包含 8个元素，然后合并每个子序列中的元素使每个子序列有序

…

一直模拟至序列与给定序列相同，再迭代一次输出

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
i = 1
while i < n and b[i - 1] <= b[i]:  # 一定要写小于等于号，切记！
    i += 1
t = i

flag = True
for j in range(t, n):
    if a[j] != b[j]:
        flag = False
        break
if flag:
    print('Insertion Sort')
    b[:t + 1] = sorted(b[:t + 1])
    print(*b)
else:
    print('Merge Sort')


    def check():  # 判断a列表和b列表是否相等
        for i in range(n):
            if a[i] != b[i]:
                return False
        return True


    k = 1
    while True:
        match = check()
        length = 1 << k  # 2的k次方
        for i in range(0, n, length):  # 第k次迭代
            # a[i:min(n, i + length)] = sorted(a[i:min(n, i + length)])
            a[i:i + length] = sorted(a[i:i + length])  # 这两行代码等价，因为python的切片操作在索引超过范围时默认切到列表最后一个元素
        if match:
            break
        k += 1
    print(*a)