摘要：通過(guò)中的源碼可以看到，在時(shí)是調(diào)用了的方法，完成排序再返回而，對(duì)原始類型，里用的是快速排序，對(duì)于對(duì)象類型，則使用歸并排序。到了快速排序升級(jí)為雙基準(zhǔn)快排雙基準(zhǔn)快排三路快排歸并排序升級(jí)為歸并排序的改進(jìn)版。

大家可能對(duì)timsort并不是很熟悉，不過(guò)說(shuō)起Collections.sort(list) 應(yīng)該并不陌生。

public static > void sort(List list) {
Object[] a = list.toArray();
Arrays.sort(a);
ListIterator i = list.listIterator();
for (int j=0; j
通過(guò)jdk6中的Collections源碼可以看到，在sort時(shí)是調(diào)用了Arrays的sort方法，完成排序再返回list
  

      public static void sort(Object[] a) {
            Object[] aux = (Object[])a.clone();
            mergeSort(aux, a, 0, a.length, 0);
        }
            private static void mergeSort(Object[] src,
                      Object[] dest,
                      int low,
                      int high,
                      int off) {
        int length = high - low;
    
        // Insertion sort on smallest arrays
            if (length < INSERTIONSORT_THRESHOLD) {
                for (int i=low; ilow &&
                 ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                        swap(dest, j, j-1);
                return;
            }
    
            // Recursively sort halves of dest into src
            int destLow  = low;
            int destHigh = high;
            low  += off;
            high += off;
            int mid = (low + high) >>> 1;
            mergeSort(dest, src, low, mid, -off);
            mergeSort(dest, src, mid, high, -off);
    
            // If list is already sorted, just copy from src to dest.  This is an
            // optimization that results in faster sorts for nearly ordered lists.
            if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
                System.arraycopy(src, low, dest, destLow, length);
                return;
            }
    
            // Merge sorted halves (now in src) into dest
            for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
                if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                    dest[i] = src[p++];
                else
                    dest[i] = src[q++];
            }
        }

而Arrays.sort()，對(duì)原始類型(int[],double[],char[],byte[])，JDK6里用的是快速排序，對(duì)于對(duì)象類型(Object[])，JDK6則使用歸并排序。
  到了jdk7,快速排序升級(jí)為雙基準(zhǔn)快排(雙基準(zhǔn)快排 vs 三路快排)；歸并排序升級(jí)為歸并排序的改進(jìn)版TimSort。
再到了JDK8， 對(duì)大集合增加了Arrays.parallelSort()函數(shù)，使用fork-Join框架，充分利用多核，對(duì)大的集合進(jìn)行切分然后再歸并排序，而在小的連續(xù)片段里，依然使用TimSort與DualPivotQuickSort。
  談到優(yōu)化過(guò)程，先來(lái)回憶一下歸并排序，長(zhǎng)度為1的數(shù)組是已經(jīng)排序好的。對(duì)長(zhǎng)度為n>1的數(shù)組，將其分為2段(partition)（最常見(jiàn)的做法是從中間分開(kāi)）。對(duì)兩段數(shù)組遞歸進(jìn)行歸并排序，完成后將其合并（merge）：通過(guò)掃描個(gè)已排序的數(shù)組并總是挑出兩者中較小數(shù)作為合并數(shù)組中的下一個(gè)元素，來(lái)將兩個(gè)已排序數(shù)組合并形成一個(gè)更大的已排序數(shù)組。
   此時(shí)如果我們遇到這樣一個(gè)數(shù)組，{5, 6, 7, 8, 9, 10, 1, 2, 3}，我們利用快排或者歸并帶來(lái)的開(kāi)銷，似乎都不劃算，因?yàn)檎б豢粗恍枰徊骄湍芡瓿膳判?。這也是timSort的一個(gè)主要優(yōu)勢(shì)，適應(yīng)性排序，先把5至10截取，1之3截取成兩段，之后再歸并排序，再來(lái)看一個(gè)數(shù)組，{64, 32, 16, 8, 4, 2, 1}，對(duì)于這樣的案例，通過(guò)適應(yīng)性排序的思路，直接反轉(zhuǎn)，再來(lái)檢查，已經(jīng)不需要額外的工作了。TimSort在此基礎(chǔ)上還進(jìn)行了其他的一些優(yōu)化，這也助推了該算法的成功。下面我們通過(guò)源碼來(lái)進(jìn)一步了解一下。
    static  void sort(T[] a, int lo, int hi, Comparator c) {
        if (c == null) {
            Arrays.sort(a, lo, hi);
            return;
        }
    
        rangeCheck(a.length, lo, hi);
        int nRemaining  = hi - lo;
        if (nRemaining < 2)
            return;  // Arrays of size 0 and 1 are always sorted
    
        // If array is small, do a "mini-TimSort" with no merges
        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.
         */
        TimSort ts = new TimSort<>(a, c);
        int minRun = minRunLength(nRemaining);
        do {
            // Identify next run
            int runLen = countRunAndMakeAscending(a, lo, hi, c);
    
            // If run is short, extend to min(minRun, nRemaining)
            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
            ts.pushRun(lo, runLen);
            ts.mergeCollapse();
    
            // Advance to find next run
            lo += runLen;
            nRemaining -= runLen;
        } while (nRemaining != 0);
    
        // Merge all remaining runs to complete sort
        assert lo == hi;
        ts.mergeForceCollapse();
        assert ts.stackSize == 1;
    }

首先是非空的判斷，如果沒(méi)有提供comparator,會(huì)調(diào)用Arrays.sort,其實(shí)也是ComparableTimSort，后面是算法的主體：如果元素個(gè)數(shù)小于2,直接返回，因?yàn)檫@兩個(gè)元素已經(jīng)排序了
如果元素個(gè)數(shù)小于一個(gè)閾值（默認(rèn)為)，調(diào)用 binarySort，這是一個(gè)不包含合并操作的 mini-TimSort。
在關(guān)鍵的 do-while 循環(huán)中，不斷地進(jìn)行排序，合并，排序，合并，一直到所有數(shù)據(jù)都處理完。
然后會(huì)找出run的最小長(zhǎng)度，少于這個(gè)最小長(zhǎng)度就需要對(duì)其進(jìn)行擴(kuò)展，再來(lái)看下binarySort
private static  void binarySort(T[] a, int lo, int hi, int start,
                                   Comparator c) {
    assert lo <= start && start <= hi;
    if (start == lo)
        start++;
    for ( ; start < hi; start++) {
        T pivot = a[start];

        // Set left (and right) to the index where a[start] (pivot) belongs
        int left = lo;
        int right = start;
        assert left <= right;
        /*
         * Invariants:
         *   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;

        /*
         * The invariants still hold: pivot >= all in [lo, left) and
         * pivot < all in [left, start), so pivot belongs at left.  Note
         * that if there are elements equal to pivot, left points to the
         * first slot after them -- that"s why this sort is stable.
         * Slide elements over to make room for pivot.
         */
        int n = start - left;  // The number of elements to move
        // Switch is just an optimization for arraycopy in default case
        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);
        }
        a[left] = pivot;
    }
}
binarySort 對(duì)數(shù)組 a[lo:hi] 進(jìn)行排序，并且a[lo:start] 是已經(jīng)排好序的。算法的思路是對(duì) a[start:hi] 中的元素，每次使用 binarySearch 為它在 a[lo:start] 中找到相應(yīng)位置，并插入。
另一個(gè)關(guān)鍵函數(shù)是mergeCollapse
/**
 * Examines the stack of runs waiting to be merged and merges adjacent runs
 * until the stack invariants are reestablished:
 *
 *     1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1]
 *     2. runLen[i - 2] > runLen[i - 1]
 *
 * This method is called each time a new run is pushed onto the stack,
 * so the invariants are guaranteed to hold for i < stackSize upon
 * entry to the method.
 */
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
        }
    }
}
它會(huì)把已經(jīng)排序的 run 合并成一個(gè)大 run，此大 run 也會(huì)排好序。并的過(guò)程會(huì)一直循環(huán)下去，一直到注釋里提到的循環(huán)不變式得到滿足。
合并的時(shí)候，有會(huì)特別的技巧。假設(shè)兩個(gè) run 是 run1,run2 ，先用 gallopRight在 run1 里使用 binarySearch 查找 run2 首元素 的位置 k, 那么 run1 中 k 前面的元素就是合并后最小的那些元素。然后，在 run2 中查找 run1 尾元素 的位置 len2 ，那么 run2 中 len2 后面的那些元素就是合并后最大的那些元素。最后，根據(jù)len1 與 len2 大小，調(diào)用 mergeLo 或者 mergeHi 將剩余元素合并。
篇幅限制，不能全都說(shuō)完了，感興趣的讀者可以移步TimeSort in java 7