归并排序

归并排序用的是分而治之的方法。也就是把列表从中间分成两个子列表，子列表又各自分为两个子列表……这样直到最后子列表中只有一个元素为止。然后再依次合并子列表。图示如下。

排序算法分而治之

合并的过程用到的两个子序列都是已经排好序的。各自遍历两个子列表的当前元素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)