归并排序我们的做法是什么？是不是将数组分成两段，然后分别对这两段进行排序，然后将这两段整合到一个数组中，这个整合的过程就用到了双指针算法，我们看上面的代码，我们两个指针p1和p2分别指向排好序的两段，然后我们判断arr[p1]和arr[p2]的值的大小，如果说，arr[p1]小的话，那就把arr[p1]填到中间数组，然后p1就往后移，同样的p2也是如此。也就是说，我们用两个指针就可以把两段排好序的数组有序地排到第三个数组当中来，原理就是，谁小谁就装进去，一直装到完为止。这样，我们会发现，对于左半段的数组上的每一个值，p1都只访问了一遍，同样对于右边的数组，p2也只是访问了一遍。也就是说，将两个排好序的数组(设为数组1和数组2)整合为一个数组（也要求排好序），假设数组1的长度为a,数组2的长度为b,那么整合操作索要进行的操作数最对为a+b。如果我们用固定某个数组的一个值，然后遍历另一个数组的所有值得做法得话，复杂度是O(a*b)，可见，用双指针算法可以达到优化效果。

双指针算法写法

本来我以为双指针算法只有一种写法，那就是y老师教的那种，但是我看了看归并排序那一题，好像那也是一种写法，而且好像更容易理解。这里把两个模板都给出来吧

这是y老师给的模板：

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < b && check(i, j)) j ++ ;

    // 具体问题的逻辑（题目要求干嘛）
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

这里解释一下上面代码的大概意思，就是说，i和j都是从0开始，然后如果j所指的东西满足某种性质的话或者他没有到达边界，那j++，用上面归并排序来说明一下：如果arr[p2]，那么我把arr[p2]存入help,然后p2++，如果下一个还满足的话，同样执行这样的操作，一直到arr[p2]>=arr[p1]的时候才停止，这时，执行上面操作的就变成p1了，然后知道数组全部判断完毕。这里我改写一下上面归并排序的代码，以方便理解：

/* 合并操作 */
void merge(int arr[], int l, int mid, int r) {
    int help[r - l + 1], i = 0;
    for (int p1 = l, p2 = mid + 1; p1 <= mid; p1++) {
        while (arr[p2] < arr[p1] && p2 <= r) help[i++] = arr[p2++];
        help[i++] = arr[p1];
    }
    /* 将help数组拷贝回给arr,注意，合并的是l到r这个区间，并不是0-尽头 */
    for (int k = 0; k < i; k++) {
        arr[l + k] = help[k];
    }
}

while(i<=a&&j<=b){
    ······
}
while(i<=a){//处理i没走完的
    ······
}
while(j<=b){
    ······
}