merge 歸并排序原理
歸并排序 == 遞歸 + 合并
合并
將兩個有序的數(shù)組合并成一個有序的大數(shù)組共缕；（從兩個小數(shù)組的第一個元素開始比較洗出，將較小的放進大數(shù)組的第一個元素；再將兩個小數(shù)組最前面的元素比較图谷，將較小的放進大數(shù)組的第二個元素....直到一個小數(shù)組先耗盡翩活，將另一個小數(shù)組直接追加到大數(shù)組后面）
遞歸
假設給定一個數(shù)組，要將其排序便贵；可以先遞歸地將數(shù)組分半菠镇，直到不能再分（此時，一個小數(shù)組只有一個元素）承璃，再將小數(shù)組逐漸合并成大數(shù)組
原地歸并
給定一個數(shù)組利耍，創(chuàng)建一個副本；將副本中元素排序后復制到原來的數(shù)組中（遞歸后，第一次是sample[0]和sample[1] 比較后隘梨，依次復制經(jīng)數(shù)組程癌；第二次是 sample[3] 和 sample[4] 比較后，復制進數(shù)組）轴猎；這樣存儲結(jié)果時不用創(chuàng)建新的數(shù)組嵌莉，節(jié)省了空間；
分解大數(shù)組
分解大數(shù)組有兩種方法：自頂向下 和 自底向上
- 自頂向下：寫一個將數(shù)組分成兩半的函數(shù)捻脖，遞歸地調(diào)用該函數(shù)直到不能再分解（此時一個小數(shù)組只包含一個元素）
- 自底向上：既然遞歸底部上一個小數(shù)組只包含一個元素锐峭，那么可以一開始就直接從副本一個一個地讀取，比較后郎仆，放進大數(shù)組中只祠；（類似于解決大問題中的小問題兜蠕，再將所有解決的小問題合并起來）
代碼
遞歸的代碼分為兩大部分：
- 合并
- 分解
- 自頂向下
- 自底向上
合并代碼
#!/usr/bin/python3
class Merge:
def merge(self, sample, low, mid, high):
aux = sample[:]
# part 1: [low:mid] index: i
# part 2: [mid+1:high] index: j
# sample -- index: n
i = low
j = mid + 1
for n in range(low, high+1):
if i > mid: # part 1 over
sample[n] = aux[j]
j += 1
elif j > high: # part 2 over
sample[n] = aux[i]
i += 1
elif aux[i] < aux[j]:
sample[n] = aux[i]
i += 1
else:
sample[n] = aux[j]
j += 1
def sortTtoB(self, sample, low, high):
mid = low + (high - low) // 2
if low >= high:
pass
else:
self.sortTtoB(sample, low, mid)
self.sortTtoB(sample, mid + 1, high)
self.merge(sample, low, mid, high)
if __name__ == '__main__':
sample = input().split()
sort = Merge()
sort.sortTtoB(sample, 0, len(sample) - 1)
for elem in sample:
print(elem, end=' ')
print()