分治法

1 归并排序就是完全遵守分治模式，直观上其操作如下：
2 分解：分解待排序的n个元素的序列成各具n/2个元素，的两个子序列
3 解决:使用归并排序递归地排序两个子序列
4 合并：合并两个已排好的子序列，
5 当待排序的序列长度为1时，递归"开始回升"在这种情况不要做任何工作, 因为长度为1的序列已经排好序了，
6 归并排序算法的关键操作是"合并"步骤中两个已拍好序的序列的合并，
7 Merge(A, p, q, r) 完成合并， 假设自数组A[p..q] 和 A[q+1..r].他合并这两个子数组，形成两个子数组形成单一的已排好序的子数组并代替当前的子数组A[p..r].


假设桌子上有两堆牌面朝上牌，，每堆都是已经拍好序，最下的牌在顶上。 输出结果：两堆牌合并成一堆，牌面朝下的放在桌上。
基本步骤:在牌面朝上的两堆牌的顶上的两张牌中选取较小的一张，将该张牌从堆中移开(该堆的顶上将显露一张新牌)并牌面朝下的凡在输出堆
重复这个步骤直到一个堆为空，这是我们只需要将剩下的堆放到输出对。
因为只需要比较顶上的两张牌，所以计算上述的步骤的时间为常量时间
最多执行n个步骤，。

下面的伪代码实现上面的思想，但有一个额外的变化，以避免在每一个基本步骤必须检查是否有堆空，
在每堆得底部放置一张哨兵牌，它包含一个特殊值，用于简化代码。这里我们使用无穷大表示我哨兵值

10*/

//伪代码
MERGE(A, q, p, r)
    n1 = q - p +1.  //第一个子序列长度
    n2 = r - q        //第二个子序列长度        
    let L[1..n1+1] and R[1..n2+1] be new arrays
    for i =1 to n1
        L[i] = A[A+i-1]
    for j = 1 to n2
        R[j] = A[q+j]
    
    L[n1+1]  = 无穷大
    L[n2+ 1] = 无穷大
    
           

    i = 1
   j = 1
    for k = p to r
        if(L[i] <= R[j])
            A[k] =L[i]
            i++
        else 
            A[k] = R[j]
            j++