## 基本思想   ：分治 
----------
## 步骤
   1.选取分界点，一般是mid
   2.递归排序算法将其分为两部分
   3.然后用循环去合并它们（注意边界问题）
例如：
   每一个元素只是被扫描一次
### (1) 

    2（i）8 8
    4 (j) 7 9
     sol =1 4 7 8 8 9
###   (2) 
     1 2 3
     3 5 8 9 10 11
     sol= 1 2 3 5 8 9 10 11(不用比较直接写到后面)
###   （3）
    3 4 7 9 10 11
    1 2 3
      sol =1 2 3 4 7 9 10 11（类似）

代码模板解释

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;//元素为0 or 1
    int mid = l + r >> 1;//选取中间值
    //划分区间
    merge_sort(q, l, mid);  
    merge_sort(q, mid + 1, r);
    //确定双指针
    int k = 0, i = l, j = mid + 1;
    //条件一
    while (i <= mid && j <= r)
       //边界判断
        if (q[i] < q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
   //条件二 
   //左边没有循环完
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    //条件三
    //右边没有循环完
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    //合并
 for (i = l,j = 0; i <= r; i ++, j ++ ) q[i]= tmp[j];
}

模板

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] < q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}