归并排序

归并是一种典型的序列操作，其工作是把两个或更多有序序列合并为一个有序序列。基于归并的思想也可也实现排序，称为归并排序。其排序思想如下：

• 初始时，把待排序序列中的 n 个记录看成 n 个有序子序列，每个子序列的长度均为1。
• 把当时序列组里的有序子序列两两归并，完成一遍后序列组里的排序序列个数减半，每个子序列的长度加倍。
• 对加长的有序子序列重复上面的操作，最终得到一个长度为 n 的有序序列。

这种归并方法称为简单的二路归并排序，也可考虑三路归并排序。

程序实现

• Python

def merge_sort(ls):
    if len(ls) <= 1:
        return ls
    mid = len(ls)//2
    # 序列左边部分
    left = merge_sort(ls[:mid])
    # 序列右边部分
    right = merge_sort(ls[mid:])
    return merge(left,right)

def merge(left,right):
    ## left部分的指针 l right部分的指针 r
    l,r = 0,0
    res = []
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            res.append(left[l])
            l += 1
        else:
            res.append(right[r])
            r += 1
    res += left[l:]
    res += right[r:]
    return res
ls = [4,7,3,3,50,9,4,8,-1,0,12,2,88]
print(merge_sort(ls))

三路并排

def merge_sort3(ls):
    if len(ls) <= 1:
        return ls
    num = len(ls)//3
    # 序列左边部分
    left = merge_sort(ls[:num])
    # 序列中间部分
    mid = merge_sort(ls[num:2*num])
    # 序列右边部分
    right = merge_sort(ls[2*num:])
    return merge3(left,mid,right)

def merge3(left,mid,right):
    l,m,r = 0,0,0
    res = []
    while l<len(left) and m<len(mid) and r<len(right):
        if left[l] < right[r]:
            if left[l] > mid[m]:
                res.append(mid[m])
                m += 1
            else:
                res.append(left[l])
                l += 1
        else:
            if right[r] > mid[m]:
                res.append(mid[m])
                m += 1
            else:
                res.append(right[r])
                r += 1
    hh = [i for i in [left[l:],mid[m:],right[r:]] if i != []]
    A,B = hh[0],hh[1]
    a,b = 0,0
    while a<len(A) and b<len(B):
        if A[a] > B[b]:
            res.append(B[b])
            b += 1
        else:
            res.append(A[a])
            a += 1
    res += A[a:]
    res += B[b:]
    return res
ls = [4,7,3,3,50,9,4,8,-1,0,12,2,88]
print(merge_sort3(ls))

复杂度和稳定性

• 复杂度：O(n log n)

• 稳定性: 稳定