根据*的定义：
插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作：首先将原始序列看成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
python源码实现：
# 模块化处理
"""
1，输入模块
2，直接插入排序判决
3，并归排序判决
4，输出
""" def input_data(): # 输入模块
d0 = int(input())
d1 = [int(x) for x in input().split()]
d2 = [int(x) for x in input().split()]
return d0, d1, d2 def dis_single(data, d0): # 逐位进行插入sort
state = 1
for i in range(len(data)):
if d0 < data[i]:
data.insert(i, d0)
state = 0
break
if state:
data.append(d0)
return data def dis_sentence(d1, d2): # 插入排序判决
data = []
state = 0
for i in range(len(d1)):
data = dis_single(data, d1[i])
d_mid = data.copy()
d_mid.extend(d1[len(d_mid):])
if d_mid == d2:
# print('Insertion Sort')
state = 1
data = dis_single(data, d1[i + 1])
d_mid = data.copy()
d_mid.extend(d1[len(d_mid):])
break
return [state, d_mid] def list_sort(d0, d1): # 两个数组进行排序合并
index = 0
for i in range(len(d1)): # 遍历d1数组
state = 1
for j in range(index, len(d0)): # 遍历d0数组
if d0[j] > d1[i]:
state = 0
index = j + 1
d0.insert(j, d1[i])
break
if state == 1: # 如果大于d0这个队列的所有值，那么直接extend所有数据
d0.extend(d1[i:])
break
return d0 def ms_sentence(d1, d2): # 并归排序判决
data = [[x] for x in d1]
state = 0
while len(data) != 1: # 循环条件
length = len(data)
half = int(length / 2) # 除2的整数部分
quo = length % 2 # 除2的商
d0_mid = []
for i in range(half):
d0_mid.append(list_sort(data[i * 2], data[i * 2 + 1]))
if quo:
d0_mid.append(data[-1])
data = d0_mid.copy()
d0_mid = []
for i in data:
for j in i:
d0_mid.append(j) if d0_mid == d2:
state = 1
if state:
break
return [state, d0_mid] def str_out(d0, d1): # 按格式进行输出
if d0[0]:
print('Insertion Sort')
str_ = str(d0[1][0])
for i in d0[1][1:]:
str_ += ' ' + str(i)
print(str_)
if d1[0]:
print('Merge Sort')
str_ = str(d1[1][0])
for i in d1[1][1:]:
str_ += ' ' + str(i)
print(str_) if __name__ == "__main__":
d0, d1, d2 = input_data()
# d1 = [int(x) for x in '3 1 2 8 7 5 9 4 6 0'.split()]
# d2 = [int(x) for x in '1 2 3 7 8 5 9 4 6 0'.split()] d3_1 = dis_sentence(d1, d2)
d3_2 = ms_sentence(d1, d2)
# print(d3_1, d3_2) str_out(d3_1, d3_2)