原理介紹

TimSort是結(jié)合了合并排序（合并排序）和插入排序（插入排序）而得出的排序算法，它在現(xiàn)實(shí)中有很好的效率.Tim Peters在2002年設(shè)計(jì)了該算法并在Python中使用是Python中l(wèi)ist.sort的默認(rèn)實(shí)現(xiàn)）。該算法找到數(shù)據(jù)中已經(jīng)排好序的塊 - 分區(qū)，每一個分區(qū)叫一個run，然后按規(guī)則合并這些run.Pyhton自從2.3版本以后一直采用Timsort算法排序，現(xiàn)在Java SE7和Android也采用Timsort算法對數(shù)組排序。
內(nèi)容
1操作
2性能
3JDK源碼
Timsort核心的過程
TimSort算法為了減少對升序部分的回饋和對降序部分的性能倒退，將輸入按其升序和降序特點(diǎn)進(jìn)行了分區(qū)。每次合并會將兩個運(yùn)行合并成一個運(yùn)行。合并的結(jié)果保存到棧中。合并直到消耗掉所有的運(yùn)行，這時將棧上剩余的跑合并到只剩一個跑為止。這時這個僅剩的跑便是排好序的結(jié)果。
綜上述過程，Timsort算法的過程包括
（0）如何數(shù)組長度小于某個值，直接用二分插入排序算法
（1）找到各個運(yùn)行，并入棧
（2）按規(guī)則合并運(yùn)行
1操作
現(xiàn)實(shí)中的大多數(shù)據(jù)通常是有部分已經(jīng)排好序的，Timsort利用了這一特點(diǎn).Timsort排序的輸入的單位不是一個個單獨(dú)的數(shù)字，而是一個個的分區(qū)。其中每一個分區(qū)叫一個“運(yùn)行“（圖1）。針對這個run序列，每次拿一個run出來進(jìn)行歸并。每次歸并會將兩個run合并成一個run。每個run最少要有2個元素.Timesor按照升序和降序劃分出每個run：run如果是是升序的，那么運(yùn)行中的后一元素要大于或等于前一元素（a [lo] <= a [lo + 1] <= a [lo + 2] <= ... ）;如果run是嚴(yán)格降序的，即運(yùn)行中的前一元素大于后一元素（a [lo]> a [lo + 1]> a [lo + 2]> ...），需要將run中的元素翻轉(zhuǎn)（這里注意降序的部分必須是“嚴(yán)格”降序才能進(jìn)行翻轉(zhuǎn)。因?yàn)門imSort的一個重要目標(biāo)是保持穩(wěn)定性的穩(wěn)定性。如果在這種情況下進(jìn)行翻轉(zhuǎn)這個算法就不穩(wěn)定）。
1.1跑的最小長度
運(yùn)行是已經(jīng)排好序的一塊分區(qū).RUN可能會有不同的長度，Timesort根據(jù)運(yùn)行的長度來選擇排序的策略。例如如果運(yùn)行的長度小于某一個值，則會選擇插入排序算法來排序。運(yùn)行的最小長度（minrun）取決于數(shù)組的大小。當(dāng)數(shù)組元素少于64個時，那么運(yùn)行的最小長度便是數(shù)組的長度，這是Timsort用插入排序算法來排序。當(dāng)數(shù)組元素大于等于63時，對于較大的陣列中，從32到65的范圍內(nèi)選擇一個稱為minrun的數(shù)，使得陣列的大小除以最小游程大小，等于或略小于2的冪。最終的算法只需要數(shù)組大小的6個最高有效位，如果剩余的位被設(shè)置，則添加一個，并將該結(jié)果用作minrun。該算法適用于所有情況，包括數(shù)組大小小于64的情況。

圖1運(yùn)行

圖2合并運(yùn)行

圖3臨時存儲空間

圖4運(yùn)行合并過程1

圖5運(yùn)行合并過程2

2性能

根據(jù)信息學(xué)理論，在平均情況下，比較排序不會比O（n log n）更快。由于Timsort算法利用了現(xiàn)實(shí)中大多數(shù)數(shù)據(jù)中會有一些排好序的區(qū)，所以Timsort會比
O對于隨機(jī)數(shù)沒有可用利用的排好序的區(qū)，Timsort時間復(fù)雜度會是log（n！）。下表是Timsort與其他比較排序算法時間復(fù)雜度（time complexity）的比較。

image

image

3JDK源碼

import java.util.Arrays;
import java.util.Comparator;

/**
 * Created by yxf on 16-5-30.
 * 這里對TimSort算法在java中的實(shí)現(xiàn)做了注釋，部分實(shí)現(xiàn)邏輯相似的注釋沒有處理，直接是原來的注釋。
 *
 */
class TimSort<T> {
    /**
     * 參與序列合并的最短長度。比這個更短的序列將會通過二叉插入排序加長。如果整個數(shù)組都比這個短，那就不會經(jīng)過歸并排序。
     * <p/>
     * 這個常量的值必須2的冪。Tim Perter 在C語言中的實(shí)現(xiàn)版本使用了64，但是根據(jù)經(jīng)驗(yàn)這里的版本使用32更合適。在最壞的情況下，使用了非2的冪賦值，就必須要重寫 {@link # minRunLength}這個方法。
     * 如果減小了這個值，就需要在構(gòu)造方法中減小stackLen的值，不然將面臨數(shù)組越界的風(fēng)險(xiǎn)。
     */
    private static final int MIN_MERGE = 32;

    /**
     * 將要被排序的數(shù)組
     */
    private final T[] a;

    /**
     * 這次排序的比較器
     */
    private final Comparator<? super T> c;

    /**
     * 判斷數(shù)據(jù)順序連續(xù)性的閾值
     * 后面結(jié)合代碼看，會容易理解一點(diǎn)
     */
    private static final int MIN_GALLOP = 7;

    private int minGallop = MIN_GALLOP;

    /**
     * 歸并排序中臨時數(shù)組的最大長度，數(shù)組的長度也可以根據(jù)需求增長。
     * 與C語言中的實(shí)現(xiàn)方式不同，對于相對較小的數(shù)組，我們不用這么大的臨時數(shù)組。這點(diǎn)改變對性能有顯著的影響
     */
    private static final int INITIAL_TMP_STORAGE_LENGTH = 256;


    /**
     * 臨時數(shù)組，根據(jù)泛型的內(nèi)容可知，實(shí)際的存儲要用Object[],不能用T[]
     */
    private T[] tmp;

    /**
     * 棧中待歸并的run的數(shù)量。一個run i的范圍從runBase[i]開始，一直延續(xù)到runLen[i]。
     * 下面這個根據(jù)前一個run的結(jié)尾總是下一個run的開頭。
     * 所以下面的等式總是成立:
     * runBase[i] + runLen[i] == runBase[i+1];
     **/

    private int stackSize = 0; //棧中run的數(shù)量
    private final int[] runBase;
    private final int[] runLen;

    /**
     * 這個構(gòu)造方法是私有的所以只能在類內(nèi)部創(chuàng)建。
     * 創(chuàng)建這個實(shí)例是為了保存一次排序過程中的狀態(tài)變量。
     */
    private TimSort(T[] a, Comparator<? super T> c) {
        this.a = a;
        this.c = c;

        // 這里是分配臨時數(shù)組的空間。SuppressWainings是為了消除泛型數(shù)組轉(zhuǎn)型的警告
        // 臨時數(shù)組的長度寫的很精煉，不明白的自己熟悉一下java位操作。
        // 結(jié)果就是 數(shù)組長度的一半或者是INITIAL_TMP_STORAGE_LENGTH
        int len = a.length;
        @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
        T[] newArray = (T[]) new Object[len < 2 * INITIAL_TMP_STORAGE_LENGTH ?
                len >>> 1 : INITIAL_TMP_STORAGE_LENGTH];
        tmp = newArray;

        /**
         * 這里是分配儲存run的棧的空間，它不能在運(yùn)行時擴(kuò)展。
         * C語言版本中的棧一直使用固定值85，但這樣對一些中小數(shù)組來說有些浪費(fèi)資源。所以，
         * 這個版本我們使用了相對較小容量的棧。
         * 在MIN_MERGE減小的時候，這些‘魔法數(shù)’可能面臨數(shù)組越界的風(fēng)險(xiǎn)。
         * */
        int stackLen = (len < 120 ? 5 :
                                 len < 1542 ? 10 :
                                 len < 119151 ? 24 : 40);
        runBase = new int[stackLen];
        runLen = new int[stackLen];
    }

    static <T> void sort(T[] a, Comparator<? super T> c) {
        sort(a, 0, a.length, c);
    }

    static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c) {
        if (c == null) {
            Arrays.sort(a, lo, hi);
            return;
        }

        rangeCheck(a.length, lo, hi);
        int nRemaining = hi - lo;
        if (nRemaining < 2)
            return;  // 長度是0或者1 就不需要排序了。

        // 小于MIN_MERGE長度的數(shù)組就不用歸并排序了，殺雞焉用宰牛刀
        if (nRemaining < MIN_MERGE) {
            int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
            binarySort(a, lo, hi, lo + initRunLen, c);
            return;
        }

        /**
         * March over the array once, left to right, finding natural runs,
         * extending short natural runs to minRun elements, and merging runs
         * to maintain stack invariant.
         *
         * 下面將進(jìn)入算法流程的主體,首先理解源碼注釋中run的含義，可以理解為升序序列的意思。
         *
         * 從左到右，遍歷一邊數(shù)組。找出自然排好序的序列(natural run)，把短的自然升序序列通過二叉查找排序
         * 擴(kuò)展到minRun長度的升序序列。最后合并棧中的所有升序序列，保證規(guī)則不變。
         */
        TimSort<T> ts = new TimSort<>(a, c); //新建TimSort對象，保存棧的狀態(tài)
        int minRun = minRunLength(nRemaining);
        do {
            //跟二叉查找插入排序一樣，先找自然升序序列
            int runLen = countRunAndMakeAscending(a, lo, hi, c);

            // If run is short, extend to min(minRun, nRemaining)
            // 如果 自然升序的長度不夠minRun，就把 min(minRun,nRemaining)長度的范圍內(nèi)的數(shù)列排好序
            if (runLen < minRun) {
                int force = nRemaining <= minRun ? nRemaining : minRun;
                binarySort(a, lo, lo + force, lo + runLen, c);
                runLen = force;
            }

            // Push run onto pending-run stack, and maybe merge
            //把已經(jīng)排好序的數(shù)列壓入棧中，檢查是不是需要合并
            ts.pushRun(lo, runLen);
            ts.mergeCollapse();

            //把指針后移runLen距離，準(zhǔn)備開始下一輪片段的排序
            lo += runLen;
            //剩下待排序的數(shù)量相應(yīng)的減少 runLen
            nRemaining -= runLen;
        } while (nRemaining != 0);

        // Merge all remaining runs to complete sort
        assert lo == hi;
        ts.mergeForceCollapse();
        assert ts.stackSize == 1;
    }

    /**
     * 被優(yōu)化的二分插入排序
     *
     * 使用二分插入排序算法給指定一部分?jǐn)?shù)組排序。這是給小數(shù)組排序的最佳方案。最差情況下
     * 它需要 O(n log n) 次比較和 O(n^2)次數(shù)據(jù)移動。
     *
     * 如果開始的部分?jǐn)?shù)據(jù)是有序的那么我們可以利用它們。這個方法默認(rèn)數(shù)組中的位置lo(包括在內(nèi))到
     * start(不包括在內(nèi))的范圍內(nèi)是已經(jīng)排好序的。
     *
     * @param a     被排序的數(shù)組
     * @param lo    待排序范圍內(nèi)的首個元素的位置
     * @param hi    待排序范圍內(nèi)最后一個元素的后一個位置
     * @param start 待排序范圍內(nèi)的第一個沒有排好序的位置，確保 (lo <= start <= hi)
     * @param c     本次排序的比較器
     */
    @SuppressWarnings("fallthrough")
    private static <T> void binarySort(T[] a, int lo, int hi, int start,
                                       Comparator<? super T> c) {
        assert lo <= start && start <= hi;
        //如果start 從起點(diǎn)開始，做下預(yù)處理；也就是原本就是無序的。
        if (start == lo)
            start++;
        //從start位置開始，對后面的所有元素排序
        for (; start < hi; start++) {
            //pivot 代表正在參與排序的值，
            T pivot = a[start];

            // Set left (and right) to the index where a[start] (pivot) belongs
            // 把pivot應(yīng)當(dāng)插入的設(shè)置的邊界設(shè)置為left和right
            int left = lo;
            int right = start;
            assert left <= right;

            /*
             * 保證的邏輯:
             *   pivot >= all in [lo, left).
             *   pivot <  all in [right, start).
             */
            while (left < right) {
                int mid = (left + right) >>> 1;
                if (c.compare(pivot, a[mid]) < 0)
                    right = mid;
                else
                    left = mid + 1;
            }
            assert left == right;

            /**
             * 此時，仍然能保證:
             * pivot >= [lo, left) && pivot < [left,start)
             * 所以，pivot的值應(yīng)當(dāng)在left所在的位置，然后需要把[left,start)范圍內(nèi)的內(nèi)容整體右移一位
             * 騰出空間。如果pivot與區(qū)間中的某個值相等，left指正會指向重復(fù)的值的后一位，
             * 所以這里的排序是穩(wěn)定的。
             */
            int n = start - left;  //需要移動的范圍的長度

            // switch語句是一條小優(yōu)化，1-2個元素的移動就不需要System.arraycopy了。
            // （這代碼寫的真是簡潔，switch原來可以這樣用）
            switch (n) {
                case 2:
                    a[left + 2] = a[left + 1];
                case 1:
                    a[left + 1] = a[left];
                    break;
                default:
                    System.arraycopy(a, left, a, left + 1, n);
            }
            //移動過之后，把pivot的值放到應(yīng)該插入的位置，就是left的位置了
            a[left] = pivot;
        }
    }

    /**
     * 這一段代碼是TimSort算法中的一個小優(yōu)化，它利用了數(shù)組中前面一段已有的順序。
     * 如果是升序，直接返回統(tǒng)計(jì)結(jié)果；如果是降序，在返回之前，將這段數(shù)列倒置，
     * 以確保這斷序列從首個位置到此位置的序列都是升序的。
     * 返回的結(jié)果是這種兩種形式的，lo是這段序列的開始位置。
     *
     * A run is the longest ascending sequence with:
     *
     * a[lo] <= a[lo + 1] <= a[lo + 2] <= ...
     *
     * or the longest descending sequence with:
     *
     * a[lo] >  a[lo + 1] >  a[lo + 2] >  ...
     *
     * 為了保證排序的穩(wěn)定性，這里要使用嚴(yán)格的降序，這樣才能保證相等的元素不參與倒置子序列的過程，
     * 保證它們原本的順序不被打亂。
     *
     * @param a  參與排序的數(shù)組
     * @param lo run中首個元素的位置
     * @param hi run中最后一個元素的后面一個位置，需要確保lo<hi
     * @param c  本次排序的比較器
     * @return 從首個元素開始的最長升序子序列的結(jié)尾位置+1 or 嚴(yán)格的降序子序列的結(jié)尾位置+1。
     */
    private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
                                                    Comparator<? super T> c) {
        assert lo < hi;
        int runHi = lo + 1;
        if (runHi == hi)
            return 1;

        // 找出最長升序序的子序列，如果降序，倒置之
        if (c.compare(a[runHi++], a[lo]) < 0) { // 前兩個元素是降序，就按照降序統(tǒng)計(jì)
            while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
                runHi++;
            reverseRange(a, lo, runHi);
        } else {                              // 前兩個元素是升序，按照升序統(tǒng)計(jì)
            while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
                runHi++;
        }

        return runHi - lo;
    }

    /**
     * 倒置數(shù)組中一段范圍的元素
     *
     * @param a  指定數(shù)組
     * @param lo 這段范圍的起始位置
     * @param hi 這段范圍的終點(diǎn)位置的后一個位置
     */
    private static void reverseRange(Object[] a, int lo, int hi) {
        hi--;
        while (lo < hi) {
            Object t = a[lo];
            a[lo++] = a[hi];
            a[hi--] = t;
        }
    }

    /**
     * 返回參與合并的最小長度，如果自然排序的長度，小于此長度，那么就通過二分查找排序擴(kuò)展到
     * 此長度。{@link #binarySort}.
     *
     * 粗略的講，計(jì)算結(jié)果是這樣的：
     *
     * 如果 n < MIN_MERGE, 直接返回 n。（太小了，不值得做復(fù)雜的操作）；
     * 如果 n 正好是2的冪，返回 n / 2；
     * 其它情況下 返回一個數(shù) k，滿足 MIN_MERGE/2 <= k <= MIN_MERGE,
     * 這樣結(jié)果就能保證 n/k 非常接近但小于一個2的冪。
     * 這個數(shù)字實(shí)際上是一種空間與時間的優(yōu)化。
     *
     * @param n 參與排序的數(shù)組的長度
     * @return 參與歸并的最短長度
     * 這段代碼寫得也很贊
     */
    private static int minRunLength(int n) {
        assert n >= 0;
        int r = 0;      // 只要不是 2的冪就會置 1
        while (n >= MIN_MERGE) {
            r |= (n & 1);
            n >>= 1;
        }
        return n + r;
    }

    /**
     * Pushes the specified run onto the pending-run stack.
     * 將指定的升序序列壓入等待合并的棧中
     *
     * @param runBase 升序序列的首個元素的位置
     * @param runLen  升序序列的長度
     */
    private void pushRun(int runBase, int runLen) {
        this.runBase[stackSize] = runBase;
        this.runLen[stackSize] = runLen;
        stackSize++;
    }

    /**
     * 檢查棧中待歸并的升序序列，如果他們不滿足下列條件就把相鄰的兩個序列合并，
     * 直到他們滿足下面的條件
     *
     * 1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1]
     * 2. runLen[i - 2] > runLen[i - 1]
     *
     * 每次添加新序列到棧中的時候都會執(zhí)行一次這個操作。所以棧中的需要滿足的條件
     * 需要靠調(diào)用這個方法來維護(hù)。
     *
     * 最差情況下，有點(diǎn)像玩2048。
     */
    private void mergeCollapse() {
        while (stackSize > 1) {
            int n = stackSize - 2;
            if (n > 0 && runLen[n - 1] <= runLen[n] + runLen[n + 1]) {
                if (runLen[n - 1] < runLen[n + 1])
                    n--;
                mergeAt(n);
            } else if (runLen[n] <= runLen[n + 1]) {
                mergeAt(n);
            } else {
                break; // Invariant is established
            }
        }
    }

    /**
     * 合并棧中所有待合并的序列，最后剩下一個序列。這個方法在整次排序中只執(zhí)行一次
     */
    private void mergeForceCollapse() {
        while (stackSize > 1) {
            int n = stackSize - 2;
            if (n > 0 && runLen[n - 1] < runLen[n + 1])
                n--;
            mergeAt(n);
        }
    }

    /**
     * 在一個序列中，將一個指定的key，從左往右查找它應(yīng)當(dāng)插入的位置；如果序列中存在
     * 與key相同的值(一個或者多個)，那返回這些值中最左邊的位置。
     *
     * 推斷： 統(tǒng)計(jì)概率的原因，隨機(jī)數(shù)字來說，兩個待合并的序列的尾假設(shè)是差不多大的，從尾開始
     * 做查找找到的概率高一些。仔細(xì)算一下，最差情況下，這種查找也是 log(n)，所以這里沒有
     * 用簡單的二分查找。
     *
     * @param key  準(zhǔn)備插入的key
     * @param a    參與排序的數(shù)組
     * @param base 序列范圍的第一個元素的位置
     * @param len  整個范圍的長度，一定有l(wèi)en > 0
     * @param hint 開始查找的位置，有0 <= hint <= len;越接近結(jié)果查找越快
     * @param c    排序，查找使用的比較器
     * @return 返回一個整數(shù) k, 有 0 <= k <=n, 它滿足 a[b + k - 1] < a[b + k]
     * 就是說key應(yīng)當(dāng)被放在 a[base + k],
     * 有 a[base,base+k) < key && key <=a [base + k, base + len)
     */
    private static <T> int gallopLeft(T key, T[] a, int base, int len, int hint,
                                      Comparator<? super T> c) {
        assert len > 0 && hint >= 0 && hint < len;
        int lastOfs = 0;
        int ofs = 1;
        if (c.compare(key, a[base + hint]) > 0) { // key > a[base+hint]
            // 遍歷右邊，直到 a[base+hint+lastOfs] < key <= a[base+hint+ofs]
            int maxOfs = len - hint;
            while (ofs < maxOfs && c.compare(key, a[base + hint + ofs]) > 0) {
                lastOfs = ofs;
                ofs = (ofs << 1) + 1;
                if (ofs <= 0)   // int overflow
                    ofs = maxOfs;
            }
            if (ofs > maxOfs)
                ofs = maxOfs;

            // 最終的ofs是這樣確定的，滿足條件 a[base+hint+lastOfs] < key <= a[base+hint+ofs]
            // 的一組
            // ofs:     1   3   7  15  31  63 2^n-1 ... maxOfs
            // lastOfs: 0   1   3   7  15  31 2^(n-1)-1  < ofs


            // 因?yàn)槟壳暗膐ffset是相對hint的，所以做相對變換
            lastOfs += hint;
            ofs += hint;
        } else { // key <= a[base + hint]
            // 遍歷左邊，直到[base+hint-ofs] < key <= a[base+hint-lastOfs]
            final int maxOfs = hint + 1;
            while (ofs < maxOfs && c.compare(key, a[base + hint - ofs]) <= 0) {
                lastOfs = ofs;
                ofs = (ofs << 1) + 1;
                if (ofs <= 0)   // int overflow
                    ofs = maxOfs;
            }
            if (ofs > maxOfs)
                ofs = maxOfs;
            // 確定ofs的過程與上面相同
            // ofs:     1   3   7  15  31  63 2^n-1 ... maxOfs
            // lastOfs: 0   1   3   7  15  31 2^(n-1)-1  < ofs

            // Make offsets relative to base
            int tmp = lastOfs;
            lastOfs = hint - ofs;
            ofs = hint - tmp;
        }
        assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;

        /*
         * 現(xiàn)在的情況是 a[base+lastOfs] < key <= a[base+ofs], 所以，key應(yīng)當(dāng)在lastOfs的
         * 右邊，又不超過ofs。在base+lastOfs-1到 base+ofs范圍內(nèi)做一次二叉查找。
         */
        lastOfs++;
        while (lastOfs < ofs) {
            int m = lastOfs + ((ofs - lastOfs) >>> 1);

            if (c.compare(key, a[base + m]) > 0)
                lastOfs = m + 1;  // a[base + m] < key
            else
                ofs = m;          // key <= a[base + m]
        }
        assert lastOfs == ofs;    // so a[base + ofs - 1] < key <= a[base + ofs]
        return ofs;
    }

    /**
     * 與gallopLeft相似，不同的是如果發(fā)現(xiàn)key的值與某些元素相等，那返回這些值最后一個元素的位置的
     * 后一個位置
     *
     * @param key  需要查找待插入位置的那個值
     * @param a    待排序的數(shù)組
     * @param base 被查找的序列中第一個元素的位置
     * @param len  被查找的序列的長度
     * @param hint 開始查找的位置，0 <= hint < len.它越接近結(jié)果所在位置，查找越快。
     * @param c    本次排序的比較器
     * @return 一個整數(shù) k,  滿足0 <= k <= n 并且 a[b + k - 1] <= key < a[b + k]
     */
    private static <T> int gallopRight(T key, T[] a, int base, int len,
                                       int hint, Comparator<? super T> c) {
        assert len > 0 && hint >= 0 && hint < len;

        int ofs = 1;
        int lastOfs = 0;
        if (c.compare(key, a[base + hint]) < 0) {
            // Gallop left until a[b+hint - ofs] <= key < a[b+hint - lastOfs]
            int maxOfs = hint + 1;
            while (ofs < maxOfs && c.compare(key, a[base + hint - ofs]) < 0) {
                lastOfs = ofs;
                ofs = (ofs << 1) + 1;
                if (ofs <= 0)   // int overflow
                    ofs = maxOfs;
            }
            if (ofs > maxOfs)
                ofs = maxOfs;

            // Make offsets relative to b
            int tmp = lastOfs;
            lastOfs = hint - ofs;
            ofs = hint - tmp;
        } else { // a[b + hint] <= key
            // Gallop right until a[b+hint + lastOfs] <= key < a[b+hint + ofs]
            int maxOfs = len - hint;
            while (ofs < maxOfs && c.compare(key, a[base + hint + ofs]) >= 0) {
                lastOfs = ofs;
                ofs = (ofs << 1) + 1;
                if (ofs <= 0)   // int overflow
                    ofs = maxOfs;
            }
            if (ofs > maxOfs)
                ofs = maxOfs;

            // Make offsets relative to b
            lastOfs += hint;
            ofs += hint;
        }
        assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;

        /*
         * Now a[b + lastOfs] <= key < a[b + ofs], so key belongs somewhere to
         * the right of lastOfs but no farther right than ofs.  Do a binary
         * search, with invariant a[b + lastOfs - 1] <= key < a[b + ofs].
         */
        lastOfs++;
        while (lastOfs < ofs) {
            int m = lastOfs + ((ofs - lastOfs) >>> 1);

            if (c.compare(key, a[base + m]) < 0)
                ofs = m;          // key < a[b + m]
            else
                lastOfs = m + 1;  // a[b + m] <= key
        }
        assert lastOfs == ofs;    // so a[b + ofs - 1] <= key < a[b + ofs]
        return ofs;
    }

    /**
     * 合并在棧中位于i和i+1的兩個相鄰的升序序列。 i必須為從棧頂數(shù)，第二和第三個元素。
     * 換句話說i == stackSize - 2 || i == stackSize - 3
     *
     * @param i 待合并的第一個序列所在的位置
     */
    private void mergeAt(int i) {
        //校驗(yàn)
        assert stackSize >= 2;
        assert i >= 0;
        assert i == stackSize - 2 || i == stackSize - 3;
        //內(nèi)部初始化
        int base1 = runBase[i];
        int len1 = runLen[i];
        int base2 = runBase[i + 1];
        int len2 = runLen[i + 1];
        assert len1 > 0 && len2 > 0;
        assert base1 + len1 == base2;

        /*
         * 記錄合并后的序列的長度；如果i == stackSize - 3 就把最后一個序列的信息
         * 往前移一位，因?yàn)楸敬魏喜⒉魂P(guān)它的事。i+1對應(yīng)的序列被合并到i序列中了，所以
         * i+1 數(shù)列可以消失了
         */
        runLen[i] = len1 + len2;
        if (i == stackSize - 3) {
            runBase[i + 1] = runBase[i + 2];
            runLen[i + 1] = runLen[i + 2];
        }
        //i+1消失了，所以長度也減下來了
        stackSize--;

        /*
         * 找出第二個序列的首個元素可以插入到第一個序列的什么位置，因?yàn)樵诖宋恢弥暗男蛄幸呀?jīng)就位了。
         * 它們可以被忽略，不參加歸并。
         */
        int k = gallopRight(a[base2], a, base1, len1, 0, c);
        assert k >= 0;
        // 因?yàn)橐雎郧鞍氩糠衷?，所以起點(diǎn)和長度相應(yīng)的變化
        base1 += k;
        len1 -= k;
        // 如果序列2 的首個元素要插入到序列1的后面，那就直接結(jié)束了,
        // ?。?！ 因?yàn)樾蛄?在數(shù)組中的位置本來就在序列1后面,也就是整個范圍本來就是有序的?。。?        if (len1 == 0)
            return;

        /*
         * 跟上面相似，看序列1的最后一個元素(a[base1+len1-1])可以插入到序列2的什么位置（相對第二個序列起點(diǎn)的位置，非在數(shù)組中的位置），
         * 這個位置后面的元素也是不需要參與歸并的。所以len2直接設(shè)置到這里，后面的元素直接忽略。
         */
        len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c);
        assert len2 >= 0;
        if (len2 == 0)
            return;

        // 合并剩下的兩個有序序列，并且這里為了節(jié)省空間，臨時數(shù)組選用 min(len1,len2)的長度
        // 優(yōu)化的很細(xì)呢
        if (len1 <= len2)
            mergeLo(base1, len1, base2, len2);
        else
            mergeHi(base1, len1, base2, len2);
    }

    /**
     * 使用固定空間合并兩個相鄰的有序序列，保持?jǐn)?shù)組的穩(wěn)定性。
     * 使用本方法之前保證第一個序列的首個元素大于第二個序列的首個元素；第一個序列的末尾元素
     * 大于第二個序列的所有元素
     *
     * 為了性能，這個方法在len1 <= len2的時候調(diào)用；它的姐妹方法mergeHi應(yīng)該在len1 >= len2
     * 的時候調(diào)用。len1==len2的時候隨便調(diào)用哪個都可以
     *
     * @param base1 index of first element in first run to be merged
     * @param len1  length of first run to be merged (must be > 0)
     * @param base2 index of first element in second run to be merged
     *              (must be aBase + aLen)
     * @param len2  length of second run to be merged (must be > 0)
     */
    private void mergeLo(int base1, int len1, int base2, int len2) {
        assert len1 > 0 && len2 > 0 && base1 + len1 == base2;

        //將第一個序列放到臨時數(shù)組中
        T[] a = this.a; // For performance
        T[] tmp = ensureCapacity(len1);
        System.arraycopy(a, base1, tmp, 0, len1);

        int cursor1 = 0;       // 臨時數(shù)組指針
        int cursor2 = base2;   // 序列2的指針，參與歸并的另一個序列
        int dest = base1;      // 保存結(jié)果的指針

        // 這里先把第二個序列的首個元素，移動到結(jié)果序列中的位置，然后處理那些不需要?dú)w并的情況
        a[dest++] = a[cursor2++];

        // 序列2只有一個元素的情況，把它移動到指定位置之后，剩下的臨時數(shù)組
        // 中的所有序列1的元素全部copy到后面
        if (--len2 == 0) {
            System.arraycopy(tmp, cursor1, a, dest, len1);
            return;
        }
        // 序列1只有一個元素的情況，把它移動到最后一個位置，為了不覆蓋，先把序列2中的元素
        // 全部移走。這個是因?yàn)樾蛄?中的最后一個元素比序列2中的所有元素都大，這是該方法執(zhí)行的條件
        if (len1 == 1) {
            System.arraycopy(a, cursor2, a, dest, len2);
            a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
            return;
        }

        Comparator<? super T> c = this.c;  // 本次排序的比較器

        int minGallop = this.minGallop;    //  "    "       "     "      "

        // 不了解break標(biāo)簽的同學(xué)要補(bǔ)補(bǔ)Java基本功了
        outer:
        while (true) {
            /*
            * 這里加了兩個值來記錄一個序列連續(xù)比另外一個大的次數(shù)，根據(jù)此信息，可以做出一些
            * 優(yōu)化
            * */
            int count1 = 0; // 序列1 連續(xù) 比序列2大多少次
            int count2 = 0; // 序列2 連續(xù) 比序列1大多少次

            /*
            * 這里是直接的歸并算法的合并的部分，這里會統(tǒng)計(jì)count1合count2,
            * 如果其中一個大于一個閾值，就會跳出循環(huán)
            * */
            do {
                assert len1 > 1 && len2 > 0;
                if (c.compare(a[cursor2], tmp[cursor1]) < 0) {
                    a[dest++] = a[cursor2++];
                    count2++;
                    count1 = 0;

                    // 序列2沒有元素了就跳出整次合并
                    if (--len2 == 0)
                        break outer;
                } else {
                    a[dest++] = tmp[cursor1++];
                    count1++;
                    count2 = 0;
                    // 如果序列1只剩下最后一個元素了就可以跳出循環(huán)
                    if (--len1 == 1)
                        break outer;
                }

            /*
            * 這個判斷相當(dāng)于 count1 < minGallop && count2 <minGallop
            * 因?yàn)閏ount1和count2總有一個為0
            * */
            } while ((count1 | count2) < minGallop);



            /*
             * 執(zhí)行到這里的話，一個序列會連續(xù)的的比另一個序列大，那么這種連續(xù)性可能持續(xù)的
             * 更長。那么我們就按照這個邏輯試一試。直到這種連續(xù)性被打破。根據(jù)找到的長度，
             * 直接連續(xù)的copy就可以了，這樣可以提高copy的效率。
             */
            do {
                assert len1 > 1 && len2 > 0;
                // gallopRight就是之前用過的那個方法
                count1 = gallopRight(a[cursor2], tmp, cursor1, len1, 0, c);
                if (count1 != 0) {
                    System.arraycopy(tmp, cursor1, a, dest, count1);
                    dest += count1;
                    cursor1 += count1;
                    len1 -= count1;
                    if (len1 <= 1) // 結(jié)尾處理退化的序列
                        break outer;
                }
                a[dest++] = a[cursor2++];
                if (--len2 == 0) //結(jié)尾處理退化的序列
                    break outer;

                count2 = gallopLeft(tmp[cursor1], a, cursor2, len2, 0, c);
                if (count2 != 0) {
                    System.arraycopy(a, cursor2, a, dest, count2);
                    dest += count2;
                    cursor2 += count2;
                    len2 -= count2;
                    if (len2 == 0)
                        break outer;
                }
                a[dest++] = tmp[cursor1++];
                if (--len1 == 1)
                    break outer;
                // 這里對連續(xù)性比另外一個大的閾值減少，這樣更容易觸發(fā)這段操作，
                // 應(yīng)該是因?yàn)榍懊娴臄?shù)據(jù)表現(xiàn)好，后面的數(shù)據(jù)類似的可能性更高？
                minGallop--;
            } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP); //如果連續(xù)性還是很大的話，繼續(xù)這樣處理s


            if (minGallop < 0)
                minGallop = 0;

            //同樣，這里如果跳出了那段循環(huán)，就證明數(shù)據(jù)的順序程度不好，應(yīng)當(dāng)增加閾值，避免浪費(fèi)資源
            minGallop += 2;
        }  //outer 結(jié)束


        this.minGallop = minGallop < 1 ? 1 : minGallop;  // Write back to field

        //這里處理收尾工作
        if (len1 == 1) {
            assert len2 > 0;
            System.arraycopy(a, cursor2, a, dest, len2);
            a[dest + len2] = tmp[cursor1]; //  Last elt of run 1 to end of merge
        } else if (len1 == 0) {
            //因?yàn)樾蛄?中的最后一個值，比序列2中的所有值都大，所以，不可能序列1空了，序列2還有元素
            throw new IllegalArgumentException(
                    "Comparison method violates its general contract!");
        } else {
            assert len2 == 0;
            assert len1 > 1;
            System.arraycopy(tmp, cursor1, a, dest, len1);
        }
    }

    /**
     * Like mergeLo, except that this method should be called only if
     * len1 >= len2; mergeLo should be called if len1 <= len2.  (Either method
     * may be called if len1 == len2.)
     *
     * @param base1 index of first element in first run to be merged
     * @param len1  length of first run to be merged (must be > 0)
     * @param base2 index of first element in second run to be merged
     *              (must be aBase + aLen)
     * @param len2  length of second run to be merged (must be > 0)
     */
    private void mergeHi(int base1, int len1, int base2, int len2) {
        assert len1 > 0 && len2 > 0 && base1 + len1 == base2;

        // Copy second run into temp array
        T[] a = this.a; // For performance
        T[] tmp = ensureCapacity(len2);
        System.arraycopy(a, base2, tmp, 0, len2);

        int cursor1 = base1 + len1 - 1;  // Indexes into a
        int cursor2 = len2 - 1;          // Indexes into tmp array
        int dest = base2 + len2 - 1;     // Indexes into a

        // Move last element of first run and deal with degenerate cases
        a[dest--] = a[cursor1--];
        if (--len1 == 0) {
            System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2);
            return;
        }
        if (len2 == 1) {
            dest -= len1;
            cursor1 -= len1;
            System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
            a[dest] = tmp[cursor2];
            return;
        }

        Comparator<? super T> c = this.c;  // Use local variable for performance
        int minGallop = this.minGallop;    //  "    "       "     "      "
        outer:
        while (true) {
            int count1 = 0; // Number of times in a row that first run won
            int count2 = 0; // Number of times in a row that second run won

            /*
             * Do the straightforward thing until (if ever) one run
             * appears to win consistently.
             */
            do {
                assert len1 > 0 && len2 > 1;
                if (c.compare(tmp[cursor2], a[cursor1]) < 0) {
                    a[dest--] = a[cursor1--];
                    count1++;
                    count2 = 0;
                    if (--len1 == 0)
                        break outer;
                } else {
                    a[dest--] = tmp[cursor2--];
                    count2++;
                    count1 = 0;
                    if (--len2 == 1)
                        break outer;
                }
            } while ((count1 | count2) < minGallop);

            /*
             * One run is winning so consistently that galloping may be a
             * huge win. So try that, and continue galloping until (if ever)
             * neither run appears to be winning consistently anymore.
             */
            do {
                assert len1 > 0 && len2 > 1;
                count1 = len1 - gallopRight(tmp[cursor2], a, base1, len1, len1 - 1, c);
                if (count1 != 0) {
                    dest -= count1;
                    cursor1 -= count1;
                    len1 -= count1;
                    System.arraycopy(a, cursor1 + 1, a, dest + 1, count1);
                    if (len1 == 0)
                        break outer;
                }
                a[dest--] = tmp[cursor2--];
                if (--len2 == 1)
                    break outer;

                count2 = len2 - gallopLeft(a[cursor1], tmp, 0, len2, len2 - 1, c);
                if (count2 != 0) {
                    dest -= count2;
                    cursor2 -= count2;
                    len2 -= count2;
                    System.arraycopy(tmp, cursor2 + 1, a, dest + 1, count2);
                    if (len2 <= 1)  // len2 == 1 || len2 == 0
                        break outer;
                }
                a[dest--] = a[cursor1--];
                if (--len1 == 0)
                    break outer;
                minGallop--;
            } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
            if (minGallop < 0)
                minGallop = 0;
            minGallop += 2;  // Penalize for leaving gallop mode
        }  // End of "outer" loop
        this.minGallop = minGallop < 1 ? 1 : minGallop;  // Write back to field

        if (len2 == 1) {
            assert len1 > 0;
            dest -= len1;
            cursor1 -= len1;
            System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
            a[dest] = tmp[cursor2];  // Move first elt of run2 to front of merge
        } else if (len2 == 0) {
            throw new IllegalArgumentException(
                    "Comparison method violates its general contract!");
        } else {
            assert len1 == 0;
            assert len2 > 0;
            System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2);
        }
    }

    /**
     * 保證臨時數(shù)組的大小能夠容納所有的臨時元素，在需要的時候要擴(kuò)展臨時數(shù)組的大小。
     * 數(shù)組的大小程指數(shù)增長，來保證線性的復(fù)雜度。
     *
     * 一次申請步長太小，申請的次數(shù)必然會增多，浪費(fèi)時間；一次申請的空間足夠大，必然會
     * 浪費(fèi)空間。正常情況下，歸并排序的臨時空間每次大的合并都會 * 2，
     * 最大長度不會超過數(shù)組長度的1/2。 這個長度于2 有著緊密的聯(lián)系。
     *
     * @param minCapacity 臨時數(shù)組需要的最小空間
     * @return tmp 臨時數(shù)組
     */
    private T[] ensureCapacity(int minCapacity) {
        // 如果臨時數(shù)組長度不夠，那需要重新計(jì)算臨時數(shù)組長度；
        // 如果長度夠，直接返回當(dāng)前臨時數(shù)組
        if (tmp.length < minCapacity) {
            // 這里是計(jì)算最小的大于minCapacity的2的冪。方法不常見，這里分析一下。
            //
            // 假設(shè)有無符號整型 k,它的字節(jié)碼如下：
            // 00000000 10000000 00000000 00000000  k
            // 00000000 11000000 00000000 00000000  k |= k >> 1;
            // 00000000 11110000 00000000 00000000  k |= k >> 2;
            // 00000000 11111111 00000000 00000000  k |= k >> 4;
            // 00000000 11111111 11111111 00000000  k |= k >> 8;
            // 00000000 11111111 11111111 11111111  k |= k >> 16
            // 上面的移位事實(shí)上只跟最高位有關(guān)系，移位的結(jié)果是最高位往后的bit全部變成了1
            // 最后 k++ 的結(jié)果 就是剛好是比 minCapacity 大的2的冪
            // 寫的真是6
            int newSize = minCapacity;
            newSize |= newSize >> 1;
            newSize |= newSize >> 2;
            newSize |= newSize >> 4;
            newSize |= newSize >> 8;
            newSize |= newSize >> 16;
            newSize++;

            if (newSize < 0) // Not bloody likely! 估計(jì)作者在這里遇到bug了
                newSize = minCapacity;
            else
                newSize = Math.min(newSize, a.length >>> 1);

            @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
            T[] newArray = (T[]) new Object[newSize];
            tmp = newArray;
        }
        return tmp;
    }

    /**
     * 檢查范圍fromIndex到toIndex是否在數(shù)組內(nèi)，如果不是拋異常
     *
     * @param arrayLen  整個數(shù)組的長度
     * @param fromIndex 該范圍的起點(diǎn)
     * @param toIndex   該范圍的終點(diǎn)
     * @throws IllegalArgumentException       if fromIndex > toIndex
     * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or toIndex > arrayLen
     */
    private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                    ") > toIndex(" + toIndex + ")");
        if (fromIndex < 0)
            throw new ArrayIndexOutOfBoundsException(fromIndex);
        if (toIndex > arrayLen)
            throw new ArrayIndexOutOfBoundsException(toIndex);
    }
}