归并排序
归并排序用的是分而治之的方法。也就是把列表从中间分成两个子列表，子列表又各自分为两个子列表……这样直到最后子列表中只有一个元素为止。然后再依次合并子列表。图示如下。
排序算法分而治之
合并的过程用到的两个子序列都是已经排好序的。各自遍历两个子列表的当前元素i和j，比较i和j，每次都选出比较小的数，分配到初始新列表的位置，注意要查看如果其中一个子序列遍历完了，直接把另外一个子序列添加到新列表剩余位置即可。
依次填入较小的序列
伪代码
merge_sort(nums)
if low>=high
return
middle=(low+high)//2
merge_sort(low, middle)
merge_sort(middle, high)
merge(nums, low, middle，high)
merge()
for i from low to high
tmp[i]=nums[i]
i=low
j=middle+1
k=low
while i<=middle and j<=high:
if tmp[i]<=tmp[j]:
nums[k]=tmp[i]
k++
i++
if tmp[i]>tmp[j]:
nums[k]=tmp[j]
k++
j++
while i<middle:
nums[k]=tmp[i]
k++
i++
while j<high:
nums[k]=tmp[j]
k++
j++
end
代码如下：
def merge(a, b):
c=[]
i=j=0
while i<len(a) and j<len(b):
if a[i]<b[j]:
c.append(a[i])
i+=1
else:
c.append(b[j])
j+=1
if j==len(b):
for g in a[i:]:
c.append(g)
else:
for g in b[j:]:
c.append(g)
#最终返回的是这个合并了的列表
return c
def merge_sort(nums):
#如果最后只剩下一个元素就返回这个元素
if len(nums)<=1:
return nums
middle=len(nums)/2
left=nums[:middle]
right=nums[middle:]
left=merge_sort(left)
right=merge_sort(right)
return merge(left, right)
