python 诠释 归并排序

踏雪寻梅

　　归并排序 相对简单 归并的含义是将两个或两个以上有序表组合成一个新的有序表：
　　假设初始序列含有n个记录，则可看成是n个有序的子序列；每个子序列的长度为1，然后两两归并，得到 （n+1）/ 2 个子序列；再两两归并……如此重复，最终得到一个有序序列，这种叫做2路归并，如图所示：

　　
　　代码实现：
　　


def merge(list_a, list_b) :
key_a,key_b = 0, 0
result = []
len_a = len(list_a)
len_b = len(list_b)
while key_a < len_a and key_b < len_b :
if list_a[key_a] <= list_b[key_b] :
result.append(list_a[key_a])
key_a += 1
else :
result.append(list_b[key_b])
key_b += 1
while key_a < len_a :
result.append(list_a[key_a])
key_a += 1
while key_b < len_b :
result.append(list_b[key_b])
key_b += 1
return result
#loop
def merge_sort1(list) :
length = len(list)
result = []
step = 1
while(step <= (length+1)/2) :
result = []
for i in range(0,length,step * 2) :
max_key = i + 2*step
result.extend(merge(list[i:i+step],list[i+step:i+step*2]))
list = result
step += 1
return result
#recursion
def merge_sort2(list):
length = len(list)
if length == 1 :
return list
else :
temp_a = merge_sort2(list[0:length/2])
temp_b = merge_sort2(list[length/2:length])
return merge(temp_a,temp_b)
if __name__ == '__main__' :
list = [49,38,65,97,76,13,27]
print merge_sort1(list)
print merge_sort2(list)
　　其中 merge_sort1 采用循环的写法，merge_sort2 采用递归写法，与快速排序和堆排序相比，归并排序是一种稳定的排序方法