2.3.1 分治法

归并排序

将一个问题，一次或多次或多次递归调用自己，分解成若干个子问题后，解决问题

图解

代码

from typing import List
import math
def merge(A:List[int],p:int,q:int,r:int):
    L = A[p:q+1]+[float('inf')]
    R = A[q+1:r+1]+[float('inf')]
    i = j = 0
    for k in range(p,r+1):
        if L[i] <= R[j]:
            A[k] = L[i]
            i+=1
        else:
            A[k] = R[j]
            j+=1
def merge_sort(A:List[int],p:int,r:int):
    if p < r:
        q = math.floor((p+r)/2)
        merge_sort(A,p,q)
        merge_sort(A,q+1,r)
        merge(A,p,q,r)
param = [5,2,4,7,1,3,2,6]
merge_sort(param,0,len(param)-1)
print(param)

2.3.2 分析分治算法

$$T(n) = \begin{cases} c, & 如果n=1\\2T(n/2)+cn, & 如果n>1\end{cases}\;=\;cn\lg n+cn$$