归并排序

public class 归并排序 {
    public static void main(String[] args) {
        int arr[] = {1,5,9,7,5,3,2,6,4,8};
        mergeSort(arr);
        for(int a:arr){
            System.out.print(a+" ");
        }
    }

    public static void mergeSort(int []arr){
        if(arr == null || arr.length < 2){
            return ;
        }
        process(arr,0,arr.length - 1);
    }

    public static void process(int []arr, int L, int R){
        if(L == R)return;
        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++];
        }
        for(i = 0 ; i < help.length; i++){
            arr[L++] = help[i];
        }
    }
}

代码来自视频学习：https://www.bilibili.com/video/BV13g41157hK?p=3