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

        // 3. 將 temp 數(shù)組，拷貝到原始數(shù)組
        // 注意：只拷貝當(dāng)前temp有效數(shù)據(jù)到對(duì)應(yīng)的原始數(shù)據(jù)中，通俗點(diǎn)說(shuō)，就是原始數(shù)組中要排序的數(shù)據(jù)，通過(guò)temp排成了有序的，然后將temp中的有序數(shù)據(jù)將原始數(shù)組中原來(lái)要排序的那部分覆蓋了就行了
        int tempL = left; // 從左邊開(kāi)始拷貝，左邊第一個(gè)值的索引
        t = 0;  // temp 中的有效值索引，有效值邊界可以通過(guò) right 判定，因?yàn)楹喜蓚€(gè)數(shù)組到 temp 中，邊界就是 right ，這里自己好好想想
        /*
         * 對(duì)于 8,4,5,7,1,3,6,2 這個(gè)數(shù)組,
         * 從棧頂開(kāi)始合并：8,4 | 5,7       1,3 | 6,2
         * 先左遞歸的話：
         * 第一次：8,4 合并：tempL=0，right=1
         * 第二次：5,7 合并：tempL=2，right=3
         * 第三次：4,8 | 5，7 進(jìn)行合并，tempL=0，right=3
         * 直到左遞歸完成，得到左側(cè)一個(gè)有序的序列：4,5,7,8 然后再開(kāi)始遞歸右邊那個(gè)無(wú)序的
         * 最后回到棧底分解成兩個(gè)數(shù)組的地方，將兩個(gè)數(shù)組合并成一個(gè)有序數(shù)組
         * 這里真的得自己想了，我只能這么說(shuō)了。
         */
        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) {
        //確保兩個(gè)數(shù)組中分別都存在至少一個(gè)數(shù)字
        if (left < right) {
            int mid = (left + right) / 2;
            // 先分解左側(cè)
            mergeSort(arr, left, mid, temp);
            // 再分解右側(cè)
            mergeSort(arr, mid + 1, right, temp);
            // 最后合并
            // 由于是遞歸，合并這里一定是棧頂?shù)南葓?zhí)行(兩邊數(shù)組各只有一個(gè)數(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);
        }
    }

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

        // 3. 將 temp 數(shù)組，拷貝到原始數(shù)組
        // 注意：只拷貝當(dāng)前temp有效數(shù)據(jù)到對(duì)應(yīng)的原始數(shù)據(jù)中，通俗點(diǎn)說(shuō)，就是原始數(shù)組中要排序的數(shù)據(jù)，通過(guò)temp排成了有序的，然后將temp中的有序數(shù)據(jù)將原始數(shù)組中原來(lái)要排序的那部分覆蓋了就行了
        int tempL = left; // 從左邊開(kāi)始拷貝，左邊第一個(gè)值的索引
        t = 0;  // temp 中的有效值索引，有效值邊界可以通過(guò) right 判定，因?yàn)楹喜蓚€(gè)數(shù)組到 temp 中，邊界就是 right ，這里自己好好想想
        /*
         * 對(duì)于 8,4,5,7,1,3,6,2 這個(gè)數(shù)組,
         * 從棧頂開(kāi)始合并：8,4 | 5,7       1,3 | 6,2
         * 先左遞歸的話：
         * 第一次：8,4 合并：tempL=0，right=1
         * 第二次：5,7 合并：tempL=2，right=3
         * 第三次：4,8 | 5，7 進(jìn)行合并，tempL=0，right=3
         * 直到左遞歸完成，得到左側(cè)一個(gè)有序的序列：4,5,7,8 然后再開(kāi)始遞歸右邊那個(gè)無(wú)序的
         * 最后回到棧底分解成兩個(gè)數(shù)組的地方，將兩個(gè)數(shù)組合并成一個(gè)有序數(shù)組
         * 這里真的得自己想了，我只能這么說(shuō)了。
         */
        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) {
        // 當(dāng)還可以分解時(shí)，就做分解操作
        if (left < right) {
            int mid = (left + right) / 2;
            // 先左遞歸分解
            doMergeSort(arr, left, mid, temp);
            // 再右遞歸分解
            doMergeSort(arr, mid + 1, right, temp);
            // 左遞歸分解到棧頂時(shí)，其實(shí)也是分為左右數(shù)組
            // 左右都到棧頂時(shí)，開(kāi)始合并：
            // 第一次：合并的是 0,1 的索引,分解到最后的時(shí)候，其實(shí)只有一個(gè)數(shù)為一組，所以第一次合并是合并兩個(gè)數(shù)字
            merge(arr, left, mid, right, temp);
        }
    }

    /**
     * 開(kāi)始合并，每次合并都是兩組，第一次合并是兩個(gè)數(shù)字，左右一組都只有一個(gè)數(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. 當(dāng)任意一邊填充完成后，剩余未填充的依次填充到 temp 數(shù)組中
        // 3. 將 temp 數(shù)組的有效內(nèi)容，拷貝會(huì)原數(shù)組，也就是將這次排序好的數(shù)組覆蓋回原來(lái)排序的原數(shù)組中

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

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

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

    /**
     * 大量數(shù)據(jù)排序時(shí)間測(cè)試
     */
    @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("共耗時(shí)：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
    }