分治法的思想：

将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解

分治法的例子：归并排序算法

用玩扑克牌的例子:

假设桌上有两堆牌面朝上的牌，每堆都已排序，最小的在最上面，我们希望把两堆牌合成一堆排好序的牌，也是小的在上面，我们的基本步骤是：将两堆牌最上面的牌互相比较，小的面朝下放新的一堆（结果堆），再次比较两堆最上面的两张牌，小的放之前的结果堆，不断重复直到其中一堆空了，再将另一堆的剩下的所有牌依次面朝下放在结果堆里。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

func MERGE ( A, p, q, r ) {
    liftN = q - p +1;
    rightN = r - q;
    L , R = new Array;
    for i = 1 to liftN {
        L[ i ] = A[p + i - 1];
    }
    for j = 1 to rightN {
        R[ j ] = A[q + i];
    }
    L[liftN + 1] = R[rightN + 1] = 无穷;
    i = j = 1;
    for k = p to r {
        if(L[ i ] < R[ j ]) {
            A[ k ] = L[ i ];
            i + +;
        } else {
            A[ k ] = R[ j ];
            j + +; 
        }
    }
}

1
2
3
4
5
6
7

func MERGE-SORT ( A, p, r ) {
if p < r
    n = (r + p) / 2;
    MERGE-SORT (A, p, n);
    MERGE-SORT (A, n + 1, r);
    MERGE (A, p, n, r);
}