/**
     * 
     *  最難的是合并,所以可以先完成合并的方法，此方法請參考 基本思想 和 思路分析中的圖解來完成
     *  動腦筋
     *
     * 
     *
     * @param arr   要排序的原始數(shù)組
     * @param left  因為是合并，所以要得到左右兩邊的的數(shù)組信息，這個是左側數(shù)組的第一個索引值
     * @param mid   因為是一個數(shù)組，標識是第一個數(shù)組的最后一個索引，即 mid+1 是右側數(shù)組的第一個索引，即中間索引
     * @param right 右側數(shù)組的結束索引，右邊數(shù)組的最后一個數(shù)
     * @param temp  臨時空間，臨時數(shù)組
     */
    public void merge(int[] arr, int left, int mid, int right, int[] temp) {
        // 定時臨時變量，用來遍歷數(shù)組比較
        int l = left;  // 左邊有序數(shù)組的初始索引
        int r = mid + 1; // 右邊有序數(shù)組的初始索引
        int t = 0; // temp 數(shù)組中當前最后一個有效數(shù)據(jù)的索引
        
        // 1. 按思路先將兩個數(shù)組（有序的）有序的合并到 temp 中
        // 因為是合并兩個數(shù)組，所以需要兩邊的數(shù)組都還有值的時候才能進行 比較合并
        // 若其中一個數(shù)組的值遍歷完了（取完了），那么就跳出該循環(huán)，把另一個數(shù)組所剩的值，直接copy進臨時數(shù)組即可
        while (l <= mid && r <= right) {
            // 如果左邊的比右邊的小，則將左邊的該元素填充到 temp 中
            // 并移動 t++,l++,好繼續(xù)下一個
            if (arr[l] < arr[r]) {
                temp[t] = arr[l];
                t++;//移動 temp 臨時數(shù)組中當前最后一個有效數(shù)據(jù)的索引
                l++; //左邊原始數(shù)組的索引移動
            }
            // 否則則將右邊的移動到 temp 中
            else {
                temp[t] = arr[r];
                t++;//移動 temp 臨時數(shù)組中當前最后一個有效數(shù)據(jù)的索引
                r++;//右邊原始數(shù)組的索引移動
            }
        }
        // 2. 如果有任意一邊的數(shù)組還有值，則依序?qū)⑹Ｓ鄶?shù)據(jù)填充到 temp 中
        // 如果左側還有值
        while (l <= mid) {
            temp[t] = arr[l];
            t++;
            l++;
        }
        // 如果右側還有值
        while (r <= right) {
            temp[t] = arr[r];
            t++;
            r++;
        }

        // 3. 將 temp 數(shù)組，拷貝到原始數(shù)組
        // 注意：只拷貝當前temp有效數(shù)據(jù)到對應的原始數(shù)據(jù)中，通俗點說，就是原始數(shù)組中要排序的數(shù)據(jù)，通過temp排成了有序的，然后將temp中的有序數(shù)據(jù)將原始數(shù)組中原來要排序的那部分覆蓋了就行了
        int tempL = left; // 從左邊開始拷貝，左邊第一個值的索引
        t = 0;  // temp 中的有效值索引，有效值邊界可以通過 right 判定，因為合并兩個數(shù)組到 temp 中，邊界就是 right ，這里自己好好想想
        /*
         * 對于 8,4,5,7,1,3,6,2 這個數(shù)組,
         * 從棧頂開始合并：8,4 | 5,7       1,3 | 6,2
         * 先左遞歸的話：
         * 第一次：8,4 合并：tempL=0，right=1
         * 第二次：5,7 合并：tempL=2，right=3
         * 第三次：4,8 | 5，7 進行合并，tempL=0，right=3
         * 直到左遞歸完成，得到左側一個有序的序列：4,5,7,8 然后再開始遞歸右邊那個無序的
         * 最后回到棧底分解成兩個數(shù)組的地方，將兩個數(shù)組合并成一個有序數(shù)組
         * 這里真的得自己想了，我只能這么說了。
         */
        System.out.println("tempL=" + tempL + "; right=" + right);
        while (tempL <= right) {
            arr[tempL] = temp[t];
            tempL++;
            t++;
        }
    }

    @Test
    public void sortTest() {
        int[] arr = new int[]{8, 4, 5, 7, 1, 3, 6, 2};
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println("排序后：" + Arrays.toString(arr));
    }

    /**
     * 分 和 合并
     */
    public void mergeSort(int[] arr, int left, int right, int[] temp) {
        //確保兩個數(shù)組中分別都存在至少一個數(shù)字
        if (left < right) {
            int mid = (left + right) / 2;
            // 先分解左側
            mergeSort(arr, left, mid, temp);
            // 再分解右側
            mergeSort(arr, mid + 1, right, temp);
            // 最后合并
            // 由于是遞歸，合并這里一定是棧頂?shù)南葓?zhí)行(兩邊數(shù)組各只有一個數(shù)時)
            // 第一次：left = 0,right=1
            // 第二次：left = 2,right=3
            // 第三次：left = 0，right=3
//            System.out.println("left=" + left + "；right=" + right);
            merge(arr, left, mid, right, temp);
        }
    }

     /**
     * 
     *  最難的是合并,所以可以先完成合并的方法，此方法請參考 基本思想 和 思路分析中的圖解來完成
     *  動腦筋
     *
     * 
     *
     * @param arr   要排序的原始數(shù)組
     * @param left  因為是合并，所以要得到左右兩邊的的數(shù)組信息，這個是左側數(shù)組的第一個索引值
     * @param mid   因為是一個數(shù)組，標識是第一個數(shù)組的最后一個索引，即 mid+1 是右側數(shù)組的第一個索引，即中間索引
     * @param right 右側數(shù)組的結束索引，右邊數(shù)組的最后一個數(shù)
     * @param temp  臨時空間，臨時數(shù)組
     */
    public void merge(int[] arr, int left, int mid, int right, int[] temp) {
        // 定時臨時變量，用來遍歷數(shù)組比較
        int l = left;  // 左邊有序數(shù)組的初始索引
        int r = mid + 1; // 右邊有序數(shù)組的初始索引
        int t = 0; // temp 數(shù)組中當前最后一個有效數(shù)據(jù)的索引
        
        // 1. 按思路先將兩個數(shù)組（有序的）有序的合并到 temp 中
        // 因為是合并兩個數(shù)組，所以需要兩邊的數(shù)組都還有值的時候才能進行 比較合并
        // 若其中一個數(shù)組的值遍歷完了（取完了），那么就跳出該循環(huán)，把另一個數(shù)組所剩的值，直接copy進臨時數(shù)組即可
        while (l <= mid && r <= right) {
            // 如果左邊的比右邊的小，則將左邊的該元素填充到 temp 中
            // 并移動 t++,l++,好繼續(xù)下一個
            if (arr[l] < arr[r]) {
                temp[t] = arr[l];
                t++;//移動 temp 臨時數(shù)組中當前最后一個有效數(shù)據(jù)的索引
                l++; //左邊原始數(shù)組的索引移動
            }
            // 否則則將右邊的移動到 temp 中
            else {
                temp[t] = arr[r];
                t++;//移動 temp 臨時數(shù)組中當前最后一個有效數(shù)據(jù)的索引
                r++;//右邊原始數(shù)組的索引移動
            }
        }
        // 2. 如果有任意一邊的數(shù)組還有值，則依序?qū)⑹Ｓ鄶?shù)據(jù)填充到 temp 中
        // 如果左側還有值
        while (l <= mid) {
            temp[t] = arr[l];
            t++;
            l++;
        }
        // 如果右側還有值
        while (r <= right) {
            temp[t] = arr[r];
            t++;
            r++;
        }

        // 3. 將 temp 數(shù)組，拷貝到原始數(shù)組
        // 注意：只拷貝當前temp有效數(shù)據(jù)到對應的原始數(shù)據(jù)中，通俗點說，就是原始數(shù)組中要排序的數(shù)據(jù)，通過temp排成了有序的，然后將temp中的有序數(shù)據(jù)將原始數(shù)組中原來要排序的那部分覆蓋了就行了
        int tempL = left; // 從左邊開始拷貝，左邊第一個值的索引
        t = 0;  // temp 中的有效值索引，有效值邊界可以通過 right 判定，因為合并兩個數(shù)組到 temp 中，邊界就是 right ，這里自己好好想想
        /*
         * 對于 8,4,5,7,1,3,6,2 這個數(shù)組,
         * 從棧頂開始合并：8,4 | 5,7       1,3 | 6,2
         * 先左遞歸的話：
         * 第一次：8,4 合并：tempL=0，right=1
         * 第二次：5,7 合并：tempL=2，right=3
         * 第三次：4,8 | 5，7 進行合并，tempL=0，right=3
         * 直到左遞歸完成，得到左側一個有序的序列：4,5,7,8 然后再開始遞歸右邊那個無序的
         * 最后回到棧底分解成兩個數(shù)組的地方，將兩個數(shù)組合并成一個有序數(shù)組
         * 這里真的得自己想了，我只能這么說了。
         */
        System.out.println("tempL=" + tempL + "; right=" + right);
        while (tempL <= right) {
            arr[tempL] = temp[t];
            tempL++;
            t++;
        }
    }

public class MyMergeSortTest {
    @Test
    public void sortTest() {
        int[] arr = new int[]{8, 4, 5, 7, 1, 3, 6, 2};
        mergeSort(arr);
        System.out.println("排序后：" + Arrays.toString(arr));
    }

    public void mergeSort(int arr[]) {
        int[] temp = new int[arr.length];
        doMergeSort(arr, 0, arr.length - 1, temp);
    }

    /**
     * 分治 與 合并
     *
     * @param arr
     * @param left
     * @param right
     * @param temp
     */
    private void doMergeSort(int[] arr, int left, int right, int[] temp) {
        // 當還可以分解時，就做分解操作
        if (left < right) {
            int mid = (left + right) / 2;
            // 先左遞歸分解
            doMergeSort(arr, left, mid, temp);
            // 再右遞歸分解
            doMergeSort(arr, mid + 1, right, temp);
            // 左遞歸分解到棧頂時，其實也是分為左右數(shù)組
            // 左右都到棧頂時，開始合并：
            // 第一次：合并的是 0,1 的索引,分解到最后的時候，其實只有一個數(shù)為一組，所以第一次合并是合并兩個數(shù)字
            merge(arr, left, mid, right, temp);
        }
    }

    /**
     * 開始合并，每次合并都是兩組，第一次合并是兩個數(shù)字，左右一組都只有一個數(shù)字
     *
     * @param arr
     * @param left
     * @param mid
     * @param right
     * @param temp
     */
    private void merge(int[] arr, int left, int mid, int right, int[] temp) {
        // 1. 按照規(guī)則，將 temp 數(shù)組填充
        // 2. 當任意一邊填充完成后，剩余未填充的依次填充到 temp 數(shù)組中
        // 3. 將 temp 數(shù)組的有效內(nèi)容，拷貝會原數(shù)組，也就是將這次排序好的數(shù)組覆蓋回原來排序的原數(shù)組中

        int l = left; // 左側數(shù)組初始索引
        int r = mid + 1; // 右側數(shù)組初始索引
        int t = 0; // 當前 temp 中有效數(shù)據(jù)的最后一個元素索引
        
        // 1. 按照規(guī)則，將 temp 數(shù)組填充
        // 當兩邊都還有數(shù)字可比較的時候，進行比較，然后填充 temp 數(shù)組
        // 只要任意一邊沒有數(shù)值可用時，就僅需到下一步驟
        while (l <= mid && r <= right) {
            // 當左邊比右邊小時，則填充到 temp 數(shù)組中
            if (arr[l] < arr[r]) {
                // 賦值完成后，t 和 l 都需要 +1，往后移動一個位置
                // t++ 是先把 t 進行賦值，再進行 t+1 操作
                temp[t++] = arr[l++];
            } else {
                // 當不滿足時，則說明 右側數(shù)字比左側的小，進行右側的填充
                temp[t++] = arr[r++];
            }
        }

        // 2. 有可能有其中一邊會有剩余數(shù)字未填充到 temp 中，進行收尾處理
        while (l <= mid) {
            temp[t++] = arr[l++];
        }
        while (r <= right) {
            temp[t++] = arr[r++];
        }

        // 3. 將這個有序數(shù)組，覆蓋會原始排序的數(shù)組中
        t = 0;
        int tempL = left; // 從左側開始，到右側結束，就是這一次要合并的兩組數(shù)據(jù)
        while (tempL <= right) {
            arr[tempL++] = temp[t++];
        }
    }
}

    /**
     * 大量數(shù)據(jù)排序時間測試
     */
    @Test
    public void bulkDataSort() {
        int max = 80000;
//        max = 8;
        int[] arr = new int[max];
        for (int i = 0; i < max; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        if (arr.length < 10) {
            System.out.println("原始數(shù)組：" + Arrays.toString(arr));
        }
        Instant startTime = Instant.now();
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
        if (arr.length < 10) {
            System.out.println("排序后：" + Arrays.toString(arr));
        }
        Instant endTime = Instant.now();
        System.out.println("共耗時：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
    }