ソートアルゴリズム-集計ソート(Java)

package com.rao.sort;

import java.util.Arrays;

/**
 * @author Srao
 * @className MergeSort
 * @date 2019/12/7 10:24
 * @package com.rao.sort
 * @Description     
 */
public class MergeSort {
    /**
     *     ：    
     * @param arr：      
     * @param left：           
     * @param right：           
     */
    public static int[] mergeSort(int[] arr, int left, int right){
        //  left == right,              
        if (left < right){
            int mid = (left + right) / 2;
            arr = mergeSort(arr, left, mid);//            
            arr = mergeSort(arr, mid+1, right);//            
            merge(arr, left, mid, right);//          ，         
        }
        return arr;
    }

    /**
     *     ：     
     * @param arr：      
     * @return
     */
    public static int[] mergeSort2(int[] arr){
        int n = arr.length;
        //            1，2，4，8，16....
        for (int i = 1; i < n; i = i+i){
            int left = 0;
            int mid = left + i - 1;
            int right = mid + i;
            while (right < n){
                merge(arr, left, mid, right);
                left = right + 1;
                mid = left + i -1;
                right = mid + i;
            }
        
            //                  ，  2，4，8...，             
            if (left < n && mid < n){
                merge(arr, left, mid, n-1);
            }
        }
        return arr;
    }

    /**
     *        
     * @param arr：      
     * @param left： left right      
     * @param mid
     * @param right
     */
    private static void merge(int[] arr, int left, int mid, int right) {
        int i = left;//         
        int j = mid+1;//         
        int k = 0;//      ，             
        int[] a = new int[right-left+1];//   
        while (i <= mid && j <= right){
            if (arr[i] < arr[j]){
                a[k] = arr[i];
                k++;
                i++;
            }else if (arr[i] >= arr[j]){
                a[k] = arr[j];
                k++;
                j++;
            }
        }
        //             
        while (i <= mid){
            a[k] = arr[i];
            k++;
            i++;
        }
        while (j <= right){
            a[k] = arr[j];
            k++;
            j++;
        }
        //               
        for (int m = 0; m < a.length; m++){
            arr[left+m] = a[m];
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 6, 9, 5, 0};
        System.out.println(Arrays.toString(arr));
        arr = mergeSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));

        int[] arr2 = {3, 6, 9, 5, 0};
        System.out.println(Arrays.toString(arr2));
        arr2 = mergeSort2(arr);
        System.out.println(Arrays.toString(arr2));


    }
}

統合ソートの考え方:
配列を2つに分けて、左右の両側をそれぞれ並べ替えて、配列が再分割できないまで下に再帰して、この時配列の中に1つの要素しかなくて、しかも1つの要素は秩序があって、更に左右の2つの部分を合併して、ずっと1つの序数のグループに再帰して合併します.