分治法三个步骤

分解：将原问题分解成一系列子问题；
解决：递归解决各个子问题，若子问题足够小，则直接求解子问题；
合并：将子问题的结果合并成原问题的解；

合并排序完全按照了上述模式
分解：将 n 个元素分成含 n / 2 个元素的子序列；
解决：用合并排序法对两个子序列递归排序；
合并：将两个子序列合并以得到已排序的结果；

合并排序过程

如图所示：

image.png

合并排序代码

func MergeSort(data []int, p int, r int) {
    if p >= r {
        return
    }
    q := p + (r-p)/2
    MergeSort(data, p, q)
    MergeSort(data, q+1, r)
    merge(data, p, q, r)
}

func merge(data []int, p int, q int, r int) {
    L := make([]int, q-p+1)
    for i := p; i <= q; i++ {
        L[i-p] = data[i]
    }
    L = append(L, math.MaxInt32)  //为了不实时排到是否最后一个数字 添加一个哨兵
    R := make([]int, r-q)
    for i := q + 1; i <= r; i++ {
        R[i-q-1] = data[i]
    }
    R = append(R, math.MaxInt32)  //添加哨兵
    i, j := 0, 0
    for k := p; k <= r; k++ {
        if L[i] < R[j] {
            data[k] = L[i]
            i++
        } else {
            data[k] = R[j]
            j++
        }
    }
}

分治法算法分析

T(n) = O(1) 当n = 1
T(n) = aT(n/b) + D(n) +C(n) 当n>2
当n = 1时 只有一个元素 显然 T(n) = O(1)
当n>1时 D(n)表示分解问题 C(n) 表示合并问题

合并排序算法分析

假设不考虑n = 1的特征情况，O(1) < O(n) 其实也包含在T(n中)
在合并算法中 a = b = 2,分解与合并问题统一为cn
所以 T(n) = 2T(n/2)+cn

由于每次分解为1/2 假设一个2^n个元素分解情况如下：

image.png

由于每层时上层的1/2, 从cn到cn/2...c 高度应该是lgn。每次需要的时间为cn
所以 T(n) = cnlgn+cn
所以合并排序时间复杂度为 O(nlgn)

回顾分治法过程

分解：将原问题分解成一系列子问题；
解决：递归解决各个子问题，若子问题足够小，则直接求解子问题；
合并：将子问题的结果合并成原问题的解；
分治法时求解复杂问题的一种很好思路。