import java.util.Arrays;
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {2,3,4,1,5,7,8,6};
        System.out.println(Arrays.toString(arr));
        mergeSort(arr,0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    /**
     *
     * @param arr  //待排序數(shù)組
     * @param low  //左邊標(biāo)識(shí)
     * @param high  //右邊標(biāo)識(shí)
     */
    public static void mergeSort(int[] arr,int low,int high){
           if(low >= high){
               return;
           }
           int mid = (low +high) >>> 1;
           mergeSort(arr,low,mid);
           mergeSort(arr,mid+1,high);
           //合并
           merge(arr, low, mid, high);
    }
    private static void merge(int[] arr, int low, int mid, int high) {
          int s1 = low;  //第一個(gè)歸并段開(kāi)始
          int s2 = mid+1 ;//第二個(gè)歸并段開(kāi)始
          //臨時(shí)數(shù)組
          int[] ret  = new int[high-low +1];
          int i = 0; //ret數(shù)組的下標(biāo)
         //歸并段有數(shù)據(jù)
         while (s1 <= mid && s2 <=high )
         {
                  //s1和s2數(shù)據(jù)比較
             if(arr[s1] <= arr[s2]){
                 ret[i++] = arr[s1++];
             }else {
                    ret[i++] = arr[s2++];
             }
         }
         //跳出循環(huán)
        while (s1 <= mid){
            ret[i++] = arr[s1++];
        }
        while (s2 <= high){
            ret[i++] = arr[s2++];
        }
        for (int j = 0; j < ret.length ; j++) {
                    arr[j+low]= ret[j];
        }
    }
}