合并排序

private void test(){
  // 源数据
   int[] arr ={1,4,7,2,3,8,9,5,6,10}
    // 目标：=====》   int[] arr = {1,2,4,9,5,6,7,9,10};
    System.out.println("排序前--------->" + Arrays.toString(arr));
    mergeSort(arr);
    System.out.println("排序之后------>" + Arrays.toString(arr));
}

@SuppressLint("NewApi")
private static int[] mergeSort(int[] arr) {
    if(arr.length <= 1) return arr;

    int mid = arr.length/2;
    int[] left = Arrays.copyOfRange(arr,0 ,mid);
    int[] right = Arrays.copyOfRange(arr,mid,arr.length);
    // 递归分割数组， 达到不可分割 为止
    left = mergeSort(left);
    right = mergeSort(right);
    
    return merge(arr,left,right);
}
private static int[] merge(int[] A, int[] B, int[] C) {
    int i = 0,j = 0 ,k = 0 ;
    int lenB =B.length;
    int lenC =C.length;
  
    while(i < lenB && j <lenC){
        if(B[i] < C[j]){
            A[k] = B[i];
            i++;
            // B 和 i 对应起来
        }else{
            A[k] = C[j];
            j++;
         // C 和 i 对应起来
        }
        k++;
    }
    //i==lenB，说明B 已经全部入A中,c剩下的直接存在A中
    if(i == lenB){
        while(j< lenC){
            A[k] = C[j];
            j++;
            k++;
        }
    }
    if(j == lenC ){
        while (i < lenB){
            A[k] = B[i];
            i++;
            k++;
        }
    }
    return A;
}