归并排序(java)

归并排序
把数组一分为二，再合并排序。
（每个子数组也需要一分为二，直到只剩一个数不能分）

时间复杂度是O（N*logN）
merge()方法的时间是N,
而process()方法的时间复杂度是O(logN)，每次都被一分为二，是二分查找的时间复杂度。

空间复杂度 O(N) ，因为用了辅助数组

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {1,2,5,4,3,6};
        process(arr,0,arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }

    }
    public static void process(int[] arr, int L, int R){
        if (L==R){
            return;
        }
        //中间位置下标
        //为什么不(L+R)/2,因为L或R可能很大，接近int最大值，相加就溢出了
        //而且右移一位 计算比 除以2快
        int mid = L + ((R-L)>>1);
        //排序左边
        process(arr,L,mid);
        //排序右边
        process(arr,mid+1,R);
        //合并
        merge(arr,L,mid,R);
    }

//合并，从小到大
    public static void merge(int[] arr,int L,int M,int R){
        int[] help = new int [R-L+1];//本轮需要合并的个数
        int i=0;
        int p1=L;//左数组的第一个
        int p2=M+1;//右数组的第一个
        //两边的数组开始，谁小谁进入辅助数组，下标++
        while (p1<=M && p2<=R){
            help[i++]=arr[p1]<=arr[p2]?arr[p1++] :arr[p2++];
        }
        //左边还有剩，全部复制到辅助数组中
        while (p1<=M){
            help[i++]=arr[p1++];
        }
        //右边还有剩，全部复制到辅助数组中
        while (p2<=R){
            help[i++]=arr[p2++];
        }
        //把从L开始合并的数组赋值给原数组
        for (int j = 0; j < help.length; j++) {
            arr[L+j]=help[j];
        }
    }
}