归并排序方法：
1、将记录分为若干个文件，每个文件先进行内部排序，这些排序好的叫做归并段或者顺串。
2、用归并将归并段由小变大，由多变少。优化
为了减少外部IO时间，要增加归并路数（多个文件同时进行归并），减少初始归并段。但增加归并路数的同时每次比较按照常规的时间也会更长，比如二路归并我们需要比较一次即可选出最小值，n路归并需要n-1次，但是我们可以利用上次比较的信息来减少多路归并的比较次数，这就是败者树。败者树：
胜者树和堆的区别：
相同的都是完全树，每次调整的时间复杂度也都是O(logn)，最大的区别就是堆的非叶子节点有包含元素，而胜者树只有叶子节点有元素，非叶子节点用来存放两个节点的胜者。由于这种结构上的差异，因此每次在调整的时候堆要分别跟两个孩子进行两次比较，而胜者树只需要跟其兄弟进行一次比较即可，效率上会高一点，有些人可能跟我一开始一样有这样的疑问，虽然你在比较次数上少了一半，但堆由于非叶子节点也含有原始数据，所以堆的树的高度会比胜者树低一些，那么需要调整的次数少了，综合起来不是差不多吗？要注意这里的树是完全二叉树，每增加一层，节点数目就增加了一倍多，因此堆的高度一般也只比胜者树矮一层，而一般树的高度都是比较高的，这样定性分析来说，堆在高度上也只有很小的优势。
胜者树和败者树的区别：
一开始我是想写代码实现败者树的，没想到理解成胜者树，实现成了胜者树。实际操作发现，胜者树每次都将胜者放在父节点上面，如果这是最终的胜者，一路上升到到根节点都是胜者的记录，这就没有必要了！于是就有了败者树，败者树的父节点存储的是败者，下次我们直接跟父节点进行比较就可以了，实际代码上减少了计算兄弟的计算量。胜者树相交于败者树代码的区别：
下面是胜者树的代码，可以看到每次更新新的数据的时候，我们要让胜者一路沿着树上浮到根节点（根节点下标为1）。很清楚地看到，我们先计算父节点的位置，然后再计算左右节点的位置，将左右节点来进行比较放到父节点，然后父节点又跟其兄弟进行比较，以此类推。
father_index = (offset+path)//2
while father_index != 0:
lc_index = father_index*2
rc_index = lc_index + 1
if loser_tree[lc_index][1] < loser_tree[rc_index][1]:
loser_tree[father_index] = loser_tree[lc_index]
else:
loser_tree[father_index] = loser_tree[rc_index]
father_index //= 2
败者树调整新加入的节点部分的代码，可以看到每次都是暂时优胜者跟上一个进行比较：
new_comer = pre_winnner
loser_tree[0] = loser_tree[new_comer]
# 对比胜者树，这里每次都只需跟上一级进行比较即可
while new_comer != 0:
if loser_tree[new_comer][1] < loser_tree[0][1]:
loser_tree[new_comer],loser_tree[0] = loser_tree[0],loser_tree[new_comer]
else:
pass
new_comer //= 2
- 置换选择排序（生成初试归并段）
为了在内存大小有限的情况下尽量增加归并段的长度。
可以用最小堆或者败者树来实现
生成的初试归并段长度、是传统方法的2倍
-最佳归并树
长度不等的归并段在归并路数相等的情况下，归并的顺序不同效率也不同，归家归并树可以减少比较次数。
胜者树全部代码：
注：本来是想实现败者树的，但是理解错误成胜者树，所以变量名称含loser不要太在意。另外我写完后才发现教科书上的图所代表的那棵树，也就是下面的loser_tree这个列表是没有包含我们分析中的叶子节点的，但我在实现上是有包含的，复制了过来，这样子代码写起来更加简洁，后来想要改，可以改，但是改的并不是很好看，所以维持现状。
# 败者树来减少多路归并所需的比较次数
BIG_NUM = 100000000
def loser_tree_merge(data):
# data是个二维数组，其横向向量个数为败者树的路数
# 每个向量所包含元素为各自路数的元素个数
paths_of_merge = len(data)
paths_length = [0]*paths_of_merge
for i in range(paths_of_merge):
paths_length[i] = len(data[i])
# 败者树是一棵完全二叉树，归并段输入的数据为树的叶子
# 完全二叉树节点个数N = N0+N1+N2，其中N0=N2+1，N0 = paths_of_merge，N1根据根据观察永远为0
loser_tree_num = paths_of_merge + (paths_of_merge - 1) + 1
loser_tree = [0]*loser_tree_num
paths_index = [0]*paths_of_merge
offset = loser_tree_num - paths_of_merge
# 填充数据到叶子节点
for i in range(paths_of_merge):
loser_tree[offset+i] = [i,data[i][paths_index[i]]]
paths_index[i] += 1
# 调整非叶子节点，注意是由最后向前调整
for i in range(offset-1,0,-1):
lc = i*2
rc = lc+1
if loser_tree[lc][1] < loser_tree[rc][1]:
loser_tree[i] = loser_tree[lc]
else:
loser_tree[i] = loser_tree[rc]
while loser_tree[1][1]!=BIG_NUM:
path,num = loser_tree[1]
print(num,end = ' ')
if paths_index[path] < paths_length[path]:
new_elem = data[path][paths_index[path]]
paths_index[path] += 1
loser_tree[offset+path] = [path, new_elem]
else:
new_elem = BIG_NUM
loser_tree[offset+path] = [path,new_elem]
father = (offset+path)//2
while father != 0:
lc = father*2
rc = lc + 1
if loser_tree[lc][1] < loser_tree[rc][1]:
loser_tree[father] = loser_tree[lc]
else:
loser_tree[father] = loser_tree[rc]
father //= 2
def main():
data = [[1,2],[3,5,8],[6,7,9]]
loser_tree_merge(data)
if __name__ == '__main__':
main()
真正的败者树来了：
# 败者树来减少多路归并所需的比较次数
BIG_NUM = 987654321
def loser_tree_merge(data):
# data是个二维数组，其横向向量个数为败者树的路数
# 每个向量所包含元素为各自路数的元素个数
paths_of_merge = len(data)
paths_length = [0]*paths_of_merge
for i in range(paths_of_merge):
paths_length[i] = len(data[i])
# 败者树是一棵完全二叉树，归并段输入的数据为树的叶子
# 完全二叉树节点个数N = N0+N1+N2，其中N0=N2+1，N0 = paths_of_merge，N1根据根据观察永远为0
loser_tree_num = paths_of_merge + (paths_of_merge - 1) + 1
loser_tree = [0]*loser_tree_num
paths_index = [0]*paths_of_merge
offset = loser_tree_num - paths_of_merge
# 败者树第一轮还需要另外记录胜者，之后就不用了
winner = [0]*loser_tree_num
# 填充数据到叶子节点
for i in range(paths_of_merge):
loser_tree[offset+i] = [i,data[i][paths_index[i]]]
winner[offset+i] = [i,data[i][paths_index[i]]]
paths_index[i] += 1
# 调整非叶子节点，注意是由最后向前调整
for i in range(offset-1,0,-1):
lc = i*2
rc = lc+1
if winner[lc][1] < winner[rc][1]:
loser_tree[i] = winner[rc]
winner[i] = winner[lc]
else:
loser_tree[i] = winner[lc]
winner[i] = winner[rc]
loser_tree[0] = winner[1]
while loser_tree[0][1]!=BIG_NUM:
path,num = loser_tree[0]
print(num,end = ' ')
pre_winnner = offset + path
if paths_index[path] < paths_length[path]:
new_elem = data[path][paths_index[path]]
paths_index[path] += 1
loser_tree[pre_winnner] = [path, new_elem]
else:
new_elem = BIG_NUM
loser_tree[pre_winnner] = [path,new_elem]
new_comer = pre_winnner
loser_tree[0] = loser_tree[new_comer]
# 对比胜者树，这里每次都只需跟上一级进行比较即可
while new_comer != 0:
if loser_tree[new_comer][1] < loser_tree[0][1]:
loser_tree[new_comer],loser_tree[0] = loser_tree[0],loser_tree[new_comer]
else:
pass
new_comer //= 2
def main():
data = [[3,5,8],[1,2,4],[6,7,9]]
loser_tree_merge(data)
if __name__ == '__main__':
main()
