归并排序

数组一分为二 再利用外排的方式去merge
外排的方式:

• 两个指针 一个额外数组 谁小拷贝谁 相等默认拷贝左边
• 一个到达之后 把另外的全部拷贝进去
• 然后把数组覆盖到原来的数组

import java.util.Arrays;

public class mergesort {
    static void merge(int[] a, int L, int R) {
        int help[] = new int[R - L + 1];//副族数组
        int m = (L + R) >> 1;
        int p1 = L;//坑!!!写成了0 真的sb  每次进来都是右边 指针一
        int p2 = m + 1;//指针二
        int i = 0;
        while (p1 <= m && p2 <= R) {
            help[i++] = a[p1] < a[p2] ? a[p1++] : a[p2++];//谁小复制谁
        }
        while (p1 <= m) {
            help[i++] = a[p1++];//把剩下的复制过去
        }
        while (p2 <= R) {
            help[i++] = a[p2++];
        }
        for (i = 0; i < help.length; i++) {
            a[L + i] = help[i];//每次的起始位置是L
        }
    }

    static void mergesort(int[] a) {
        if (a == null || a.length < 2) {//边界条件
            return;
        }
        mergesort(a, 0, a.length - 1);//进入递归函数
    }

    static void mergesort(int[] a, int l, int r) {
        if (l >= r) {
            return;
        }
        int m = (l + r) >> 1;//坑!!!
        mergesort(a, l, m);//左边递归
        mergesort(a, m + 1, r);//右边递归
        merge(a, l, r);//类似外排合并
    }


 }