排序算法（六）- TimSort

前言

我们在上篇文章 排序算法（五）-双调排序 介绍了双调排序，今天我们来看一下另一种排序算法 —— TimSort。

TimSort是Tim Peters发明的一种混合排序，最早是Python语言的内置排序算法。

关于Python内置的TimSort描述可以查看该 文档。

关于TimSort的理论基础，可以查看该篇论文 Optimistic Sorting and Information Theoretic Complexity，这篇论文论证了插入排序和归并排序合并后效率提高的可能性，即TimSort的理论基础。

Java自Java 7 后加入TimSort，其实现参考了Python版本的实现，我们可以在JDK源码的util包下找到它，java.util.TimSort，这个class不是public的，我们无法直接调用，只能够通过Java提供的sort方法等间接调用它。

为什么引入了TimSort呢？我们慢慢来看下吧。

正文

TimSort的排序原理

说到排序算法，我们就先来了解下排序算法的基本原理，这样有助于我们更快理解算法本身。

TimSort作为一种混合排序算法，其内部使用了插入排序（准确的说是二分插入排序）和归并排序。

根据我们之前说到的，归并排序是一种时间复杂度很平均（O(n * log n) 排序算法，其缺点一个是如果两个序列长度相差较大（一个长序列和一个短序列归并），排序效率无法体现；另一个是当数组长度很小时，归并的效率也不是很高且浪费空间。

对于插入排序，虽然时间复杂度为（O(n^2)），但是较小数据量下，其表现也不错，在一部分数据已经排序的情况下，其表现要更好，而使用插入排序的变种二分插入排序，虽不能减少移动次数，但减少了比较次数。

说到这里，我们再说TimSort基于的一个简单事实：数组中的数据都是部分有序（升序或降序）的。

什么意思呢？ 比如 数组[9,8,5,7,3,9,1,3,4,6,0,5,3]，可以看到里面部分数据[9,8,5],[1,3,4,6]等等有序。

这对插入排序是十分友好的。

Timsort排序算法可以概括成如下几步：

1. 把待排数组划分成一个个run，当然run不能太短，长度最小阈值为minRun；
2. run的划分规则：从数组最小下标low开始，寻找连续有序部分（连续逆序也算，寻找的时候会把这段顺序反过来），如果这段有序部分长度小于minRun，就用二分插入排序补充到minRun；
3. 将run入栈，当栈顶的run的长度不满足下列约束条件中任意一个时，

   runLen[n-1] > runLen[n] + runLen[n+1]
   runLen[n] > runLen[n+1]

   则利用归并排序将其中最短的2个run合并成一个新run；
4. 最后会有一次强制合并合并所有栈内剩余所有run，最终栈空，生成有序数组。

TimSort算法的原理可以用下图大致表示：

这儿我们设minRun = 4.

如上图可以清晰的看到TimSort的排序过程。

TimSort源码分析

下面我们来分析下TimSort的源码。

它的主要入口为sort方法，sort方法参数说明如下：

T[] a : 表示待排序数组；
int lo：排序的起始位置，如果排整个数组传0即可；
int hi：排序的终止位置，排整个数组传数组长度n即可；
Comparator<? super T> c：数据的比较规则；
T[] work： 合并所需的临时存储空间设置，一般不需要我们设置，会有默认值，传null即可；
int workBase ：合并所需的临时存储空间分片基数值，一般不需要我们设置，会有默认值，传0即可；
int workLen：合并所需的临时存储空间默认长度，一般不需要我们设置，会有默认值，传0即可。

可以看到传入的排序位置lo和hi，如果长度小于2，直接返回，如果小于32，就做mini-TimSort，迷你TimSort就相当于上面图中说的部分有序的二分插入排序。

再来看下下面部分。

TimSort先计算出该数组的minRun，然后开始处理数据，拿到有序长度，判断是否小于minRun，小于的话就用插入排序补齐，然后入栈，看看是否需要进行归并排序，移动位置到下一个run，重复上述过程，最后在进行一次归并排序，得到有序数据。

二分插入排序法的源码如下：

private static <T> void binarySort(T[] a, int lo, int hi, int start,Comparator<? super T> 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;
    }
}

计算有序部分长度（如果逆序有序就把数据处理成正序）的源码如下：

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;
    // Find end of run, and reverse range if descending
    if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
        while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
            runHi++;
        reverseRange(a, lo, runHi);
    } else {                              // Ascending
        while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
            runHi++;
    }
    return runHi - lo;
}
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;
    }
}    

获取该数组的minRun的相关代码如下：

private static int minRunLength(int n) {
    assert n >= 0;
    int r = 0;      // Becomes 1 if any 1 bits are shifted off
    while (n >= MIN_MERGE) {
        r |= (n & 1);
        n >>= 1;
    }
    return n + r;
}

可以看到如果入参n小于MIN_MERGE（32）时，会直接返回n，因为太小了；如果n恰好是2的幂，则返回MIN_MERGE/2；否则返回一个int k, MIN_MERGE/2 <= k <= MIN_MERGE，使n/k接近但小于2的幂次值。

关于这样设计的基本原理，可以查看Tim在Python上关于它的描述文档 listsort.txt。

检测并合并不符合条件的栈元素的相关代码如下：

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
        }
    }
}

我们可以看到它的合并条件，如上面提到的。

关于它的合并方法mergeAt，内容较多，在这儿就不展示了。

最后强制合并栈元素的代码如下：

private void mergeForceCollapse() {
    while (stackSize > 1) {
        int n = stackSize - 2;
        if (n > 0 && runLen[n - 1] < runLen[n + 1])
            n--;
        mergeAt(n);
    }
}

该方法最终会将栈内元素合并为1个，即run[0],即有序数组。

初始化栈空间及归并缓存空间代码如下：

private TimSort(T[] a, Comparator<? super T> c, T[] work, int workBase, int workLen) {
     this.a = a;
     this.c = c;
     // Allocate temp storage (which may be increased later if necessary)
     int len = a.length;
     int tlen = (len < 2 * INITIAL_TMP_STORAGE_LENGTH) ?
         len >>> 1 : INITIAL_TMP_STORAGE_LENGTH;
     if (work == null || workLen < tlen || workBase + tlen > work.length) {
         @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
         T[] newArray = (T[])java.lang.reflect.Array.newInstance
             (a.getClass().getComponentType(), tlen);
         tmp = newArray;
         tmpBase = 0;
         tmpLen = tlen;
     }
     else {
         tmp = work;
         tmpBase = workBase;
         tmpLen = workLen;
     }
     int stackLen = (len <    120  ?  5 :
                     len <   1542  ? 10 :
                     len < 119151  ? 24 : 49);
     runBase = new int[stackLen];
     runLen = new int[stackLen];
 }

Java版本TimSort曾经的Bug

在JDK1.7时候，TimSort曾经有一个bug，会引发数组下标越界异常。

PS：这个Bug已经被fix了。

bug详情可参考如下链接 JDK-8011944 : Sort fails with ArrayIndexOutOfBoundsException。

关于这篇bug的发现验证解决可参考这篇pdf,OpenJDK’s java.utils.Collection.sort() is broken:The good, the bad and the worst case?。

我们这儿简单说下这个bug吧。

上面我们看到TimSort栈内元素合并的条件，它的目的在于尽量保证两个要进行归并排序的数组长度大致相同。

所以栈内所有run应该满足如下条件：

2 <= i <= StackSize-1
runLen[n-1] > runLen[n] + runLen[n+1]
runLen[n] > runLen[n+1]

我们看mergeCollapse方法也能验证这一点。

大多数情况下我们检查栈顶的3个元素就能满足约束条件，但是一些特殊情况下就不行了，比如下面的这个栈：

120, 80, 25, 20, 30

根据源码，因为25 < 20 + 30，25 < 30，所以将25和20两个run进行合并，此时栈内的情况变为

120, 80, 45, 30

由于80 > 45 + 30，45 > 30，满足约束条件，此时归并就终止了。但是注意栈里的其他run，120 < 80 + 45，这是不满足约束条件的，而由于我们只判断了栈顶的run，因此在这里就留下了“隐患”。

大多数情况下，这并不是什么问题，因为TimSort最终可以通过最后的强制归并将数据排序合并。

但是Bug发现者构造了一个非常精致的Array，成功的让Timsort算法抛出java.lang.ArrayIndexOutOfBoundsException，代码如下：

public class BreakTimSort {

    private static final int MIN=16;
    ArrayDeque<Integer> chunks = new ArrayDeque<Integer>();

    private static final int BOUND1 = 2*MIN+1;
    private static final int BOUND2 = BOUND1+MIN+2;
    private static final int BOUND3 = BOUND1+1+BOUND2;
    private static final int BOUND4 = BOUND2+1+BOUND3;
    private static final int BOUND5 = BOUND3+1+BOUND4;

    public int build(int size, int B) {
        chunks.addFirst(B);
        if (size < BOUND1) {
            chunks.addFirst(size);
            return size;
        }

        int asize = (size+2)/2;
        if (size >= BOUND2 && asize < BOUND1)
            asize = BOUND1;
        else if (size >= BOUND3 && asize < BOUND2)
            asize = BOUND2;
        else if (size >= BOUND4 && asize < BOUND3)
            asize = BOUND3;
        else if (size >= BOUND5 && asize < BOUND4)
            asize = BOUND4;
        if (size - asize >= B)
            throw new AssertionError( "  " +size+ " , " +asize+ " , " +B);
        return build (asize, size - asize);
    }

    public void run() {
        chunks.addFirst(MIN);

        int B = MIN+4;
        int A = B + MIN + 1;

        for (int i = 0; i< 8; i++) {
            int eps = build(A, B);
            B = B+A+1;
            A = B+eps + 1;
        }
        chunks.addFirst(B);
        chunks.addFirst(A);
        int total = 0;
        for (Integer len: chunks) {
            total += len;
        }
        int pow = MIN;
        while (pow < total)
            pow += pow;
        chunks.addLast(pow-total);
        System.err.println( " Total:  " +total);
        Object[] array = new Object[pow];
        int off = 0;
        int pos = 0;
        for (Integer len: chunks) {
            for (int i = 0; i < len; i++) {
                array[pos++] = Integer.valueOf(i == 0 ? 0 : 1);
            }
            off++;
        }
        Arrays.sort(array);
    }

    public static void main(String[] param) {
        new BreakTimSort().run();
    }
}

PS:这段代码我们现在测试是没有问题的，因为这个bug已经被Fix了，如果想复现这个bug，可以下载 JDK - 1.7.0_07 版本。

这个bug出现的原因是TimSort初始化时会申请栈空间，如下：

int stackLen = (len <    120  ?  5 :
                        len <   1542  ? 10 :
                        len < 119151  ? 24 : 49);
        runBase = new int[stackLen];
        runLen = new int[stackLen];

在JDK - 1.7.0_07版本它是这样的：

int stackLen = (len <    120  ?  5 :
                len <   1542  ? 10 :
                len < 119151  ? 19 : 40);
        runBase = new int[stackLen];
        runLen = new int[stackLen];

可以看到有几个数字不一样，是的，不要小看这几个“魔法”数字。

这几个数字怎么来呢？ 我们栈归并的条件上面有提到，它其实就是函数 F(n) < F(n-1) + F(n-2) +1，我们设F(n) = F(n-1) + F(n-2) +1，这个函数是不是很熟悉，在 SmoothSort里我们有提到过，不过我们这里的起始是0，第一个元素是minRun。

我们设minRun为16（上面的minRunLength方法，可以看到minRun最小值为MIN_MERGE/2 = 16），如下程序：

PS:minRun越小，数组长度固定的情况下，分的份数就越多，理论需要的栈数量也越多。栈数量要多，少的话可能出现数组下标越界问题。

private static void getNum(){
    int[] k = new int[]{5,10,19,40};
    for(int p=0;p<k.length;p++){
        long sum =0;
        for(int i=0;i<k[p];i++){
            sum += function(i);
        }
        System.out.println(k[p] +"--->"+sum);
    }

}
private static long function(long n){
    if(n ==0){
        return 0;
    }else if(n==1){
        return 16;
    }
    return function(n-1) + function(n-2)+1;
}

如下输出：

5--->119
10--->1541
19--->119150
40--->2917196495

当为40的时候已经超出了int最大值。

上述数据是在理想情况下，即 F(n) = F(n-1) + F(n-2) +1，但是实际上会有不满足的情况，这时候需要的栈大小就应该大一些，因而就出现了我们上述所说的异常。

关于实际需要的栈大小，上面PDF中给出了，可以直接查看，如下：

array size	64	128	160	65536	131072	67108864	1073741824
required stack size	3	4	5	21	23	41	49
runLen.length	5	10	10	19 (24)	40	40	40

可以看到JDK1.8中长度已经变为了5,10,24,49，相当于修复了这个bug。

上述PDF中还给出了一种出现无法合并的栈的情况的解决方法：

private void mergeCollapse() {
    while (stackSize > 1) {
        int n = stackSize - 2;
        if (n > 0 && runLen[n-1] <=runLen[n] + runLen[n + 1]
                ||n-1 > 0 && runLen[n-2] <=runLen[n] + runLen[n-1]){
            if (runLen[n-1] <runLen[n + 1]) {
                n--;
            }
        } else if (n < 0 || runLen[n] > runLen[n + 1]) {
            break; // Invariant is established
        }
        mergeAt(n);
    }
}

相当于增加了n-1 > 0 && runLen[n-2] <= runLen[n] + runLen[n-1] 这部分，把栈顶的第4个元素也加入了判断。

但是Java社区JDK1.8中并未采用这段代码，还是原来的3层栈元素判断，只是变更了栈的长度作为解决办法，原因不详。

以上就是TimSort曾经出现的bug。

测试TimSort

我们将TimSort源码中的泛型去掉，排序数组改为int[]，测试下TimSort的性能。

public class TimSort {

    private static final int MIN_MERGE = 32;

    private final int[] a;

    private static final int  MIN_GALLOP = 7;

    private int minGallop = MIN_GALLOP;

    private static final int INITIAL_TMP_STORAGE_LENGTH = 256;

    private int[] tmp;
    private int tmpBase;
    private int tmpLen;

    private int stackSize = 0;
    private final int[] runBase;
    private final int[] runLen;

    private TimSort(int[] a, int[] work, int workBase, int workLen) {
        this.a = a;

        // Allocate temp storage (which may be increased later if necessary)
        int len = a.length;
        int tlen = (len < 2 * INITIAL_TMP_STORAGE_LENGTH) ?
                len >>> 1 : INITIAL_TMP_STORAGE_LENGTH;
        if (work == null || workLen < tlen || workBase + tlen > work.length) {
            tmp = new int[tlen];
            tmpBase = 0;
            tmpLen = tlen;
        }
        else {
            tmp = work;
            tmpBase = workBase;
            tmpLen = workLen;
        }

        int stackLen = (len <    120  ?  5 :
                len <   1542  ? 10 :
                        len < 119151  ? 24 : 49);
        runBase = new int[stackLen];
        runLen = new int[stackLen];
    }


    static void sort(int[] a, int lo, int hi,int[] work, int workBase, int workLen) {
        assert a != null && lo >= 0 && lo <= hi && hi <= a.length;

        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);
            binarySort(a, lo, hi, lo + initRunLen);
            return;
        }

        TimSort ts = new TimSort(a,work, workBase, workLen);
        int minRun = minRunLength(nRemaining);
        do {
            // Identify next run
            int runLen = countRunAndMakeAscending(a, lo, hi);

            // 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);
                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;
    }

    private static void binarySort(int[] a, int lo, int hi, int start) {
        assert lo <= start && start <= hi;
        if (start == lo) {
            start++;
        }
        for ( ; start < hi; start++) {
            int 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 (pivot<a[mid]) {
                    right = mid;
                }else {
                    left = mid + 1;
                }
            }
            assert left == right;

            // The number of elements to move
            int n = start - left;
            // 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;
        }
    }

    private static int countRunAndMakeAscending(int[] a, int lo, int hi) {
        assert lo < hi;
        int runHi = lo + 1;
        if (runHi == hi) {
            return 1;
        }

        // Find end of run, and reverse range if descending
        // Descending
        if (a[runHi++]< a[lo]) {
            while (runHi < hi && a[runHi]< a[runHi - 1]) {
                runHi++;
            }
            reverseRange(a, lo, runHi);
        // Ascending
        } else {
            while (runHi < hi && a[runHi]>= a[runHi - 1]) {
                runHi++;
            }
        }

        return runHi - lo;
    }

    private static void reverseRange(int[] a, int lo, int hi) {
        hi--;
        while (lo < hi) {
            int t = a[lo];
            a[lo++] = a[hi];
            a[hi--] = t;
        }
    }

    private static int minRunLength(int n) {
        assert n >= 0;
        // Becomes 1 if any 1 bits are shifted off
        int r = 0;
        while (n >= MIN_MERGE) {
            r |= (n & 1);
            n >>= 1;
        }
        return n + r;
    }

    private void pushRun(int runBase, int runLen) {
        this.runBase[stackSize] = runBase;
        this.runLen[stackSize] = runLen;
        stackSize++;
    }

    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
            }
        }
    }

    private void mergeForceCollapse() {
        while (stackSize > 1) {
            int n = stackSize - 2;
            if (n > 0 && runLen[n - 1] < runLen[n + 1]) {
                n--;
            }
            mergeAt(n);
        }
    }

    private void mergeAt(int i) {
        assert stackSize >= 2;
        assert i >= 0;
        assert i == stackSize - 2 || i == stackSize - 3;

        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;

        runLen[i] = len1 + len2;
        if (i == stackSize - 3) {
            runBase[i + 1] = runBase[i + 2];
            runLen[i + 1] = runLen[i + 2];
        }
        stackSize--;

        int k = gallopRight(a[base2], a, base1, len1, 0);
        assert k >= 0;
        base1 += k;
        len1 -= k;
        if (len1 == 0) {
            return;
        }

        len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1);
        assert len2 >= 0;
        if (len2 == 0) {
            return;
        }

        // Merge remaining runs, using tmp array with min(len1, len2) elements
        if (len1 <= len2) {
            mergeLo(base1, len1, base2, len2);
        }else {
            mergeHi(base1, len1, base2, len2);
        }
    }

    private static int gallopLeft(int key, int[] a, int base, int len, int hint) {
        assert len > 0 && hint >= 0 && hint < len;
        int lastOfs = 0;
        int ofs = 1;
        if (key> a[base + hint]) {
            // Gallop right until a[base+hint+lastOfs] < key <= a[base+hint+ofs]
            int maxOfs = len - hint;
            while (ofs < maxOfs && key> a[base + hint + ofs]) {
                lastOfs = ofs;
                ofs = (ofs << 1) + 1;
                // int overflow
                if (ofs <= 0) {
                    ofs = maxOfs;
                }
            }
            if (ofs > maxOfs) {
                ofs = maxOfs;
            }

            // Make offsets relative to base
            lastOfs += hint;
            ofs += hint;
        } else { // key <= a[base + hint]
            // Gallop left until a[base+hint-ofs] < key <= a[base+hint-lastOfs]
            final int maxOfs = hint + 1;
            while (ofs < maxOfs && key<= a[base + hint - ofs]) {
                lastOfs = ofs;
                ofs = (ofs << 1) + 1;
                // int overflow
                if (ofs <= 0) {
                    ofs = maxOfs;
                }
            }
            if (ofs > maxOfs) {
                ofs = maxOfs;
            }

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

        lastOfs++;
        while (lastOfs < ofs) {
            int m = lastOfs + ((ofs - lastOfs) >>> 1);

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

    private static int gallopRight(int key, int[] a, int base, int len,int hint) {
        assert len > 0 && hint >= 0 && hint < len;

        int ofs = 1;
        int lastOfs = 0;
        if (key< a[base + hint]) {
            // Gallop left until a[b+hint - ofs] <= key < a[b+hint - lastOfs]
            int maxOfs = hint + 1;
            while (ofs < maxOfs && key< a[base + hint - ofs]) {
                lastOfs = ofs;
                ofs = (ofs << 1) + 1;
                // int overflow
                if (ofs <= 0) {
                    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 && key>= a[base + hint + ofs]) {
                lastOfs = ofs;
                ofs = (ofs << 1) + 1;
                // int overflow
                if (ofs <= 0) {
                    ofs = maxOfs;
                }
            }
            if (ofs > maxOfs) {
                ofs = maxOfs;
            }

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

        lastOfs++;
        while (lastOfs < ofs) {
            int m = lastOfs + ((ofs - lastOfs) >>> 1);

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

    private void mergeLo(int base1, int len1, int base2, int len2) {
        assert len1 > 0 && len2 > 0 && base1 + len1 == base2;

        // Copy first run into temp array
        // For performance
        int[] a = this.a;
        int[] tmp = ensureCapacity(len1);
        // Indexes into tmp array
        int cursor1 = tmpBase;
        // Indexes int a
        int cursor2 = base2;
        // Indexes int a
        int dest = base1;
        System.arraycopy(a, base1, tmp, cursor1, len1);

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

        int minGallop = this.minGallop;
        outer:
        while (true) {
            // Number of times in a row that first run won
            int count1 = 0;
            // Number of times in a row that second run won
            int count2 = 0;

            do {
                assert len1 > 1 && len2 > 0;
                if (a[cursor2]< tmp[cursor1]) {
                    a[dest++] = a[cursor2++];
                    count2++;
                    count1 = 0;
                    if (--len2 == 0) {
                        break outer;
                    }
                } else {
                    a[dest++] = tmp[cursor1++];
                    count1++;
                    count2 = 0;
                    if (--len1 == 1) {
                        break outer;
                    }
                }
            } while ((count1 | count2) < minGallop);

            do {
                assert len1 > 1 && len2 > 0;
                count1 = gallopRight(a[cursor2], tmp, cursor1, len1, 0);
                if (count1 != 0) {
                    System.arraycopy(tmp, cursor1, a, dest, count1);
                    dest += count1;
                    cursor1 += count1;
                    len1 -= count1;
                    // len1 == 1 || len1 == 0
                    if (len1 <= 1) {
                        break outer;
                    }
                }
                a[dest++] = a[cursor2++];
                if (--len2 == 0) {
                    break outer;
                }

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

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


    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
        // For performance
        int[] a = this.a;
        int[] tmp = ensureCapacity(len2);
        int tmpBase = this.tmpBase;
        System.arraycopy(a, base2, tmp, tmpBase, len2);
        // Indexes into a
        int cursor1 = base1 + len1 - 1;
        // Indexes into tmp array
        int cursor2 = tmpBase + len2 - 1;
        // Indexes into a
        int dest = base2 + len2 - 1;

        // Move last element of first run and deal with degenerate cases
        a[dest--] = a[cursor1--];
        if (--len1 == 0) {
            System.arraycopy(tmp, tmpBase, 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;
        }

        int minGallop = this.minGallop;
        outer:
        while (true) {
            // Number of times in a row that first run won
            int count1 = 0;
            // Number of times in a row that second run won
            int count2 = 0;

            do {
                assert len1 > 0 && len2 > 1;
                if (tmp[cursor2]< a[cursor1]) {
                    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);

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

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

    private int[] ensureCapacity(int minCapacity) {
        if (tmpLen < minCapacity) {
            // Compute smallest power of 2 > minCapacity
            int newSize = minCapacity;
            newSize |= newSize >> 1;
            newSize |= newSize >> 2;
            newSize |= newSize >> 4;
            newSize |= newSize >> 8;
            newSize |= newSize >> 16;
            newSize++;

            // Not bloody likely!
            if (newSize < 0) {
                newSize = minCapacity;
            }else {
                newSize = Math.min(newSize, a.length >>> 1);
            }

            tmp = new int[newSize];
            tmpLen = newSize;
            tmpBase = 0;
        }
        return tmp;
    }
    
    public static void main(String[] args) {
            int[] a = new int[100000000];
            Random r = new Random();
            for (int i = 0; i < a.length; i++) {
                a[i] = r.nextInt(100000000);
            }
            System.out.println("TimSort排序开始：");
            long start = System.currentTimeMillis();
            sort(a,0,a.length,null,0,0);
            System.out.println("TimSort耗时："+(System.currentTimeMillis()-start)+"ms");
            System.out.println("TimSort排序完成！");
            System.out.println("数组是否有序："+isOrdered(a));
    }
}    

有如下结果，排序1亿数据耗时在17s左右。

TimSort排序开始：
TimSort耗时：17831ms
TimSort排序完成！
数组是否有序：true

TimSort的时间复杂度如下：

• 时间复杂度（最好）：O(n)
• 时间复杂度（平均）：O(n * log n)
• 时间复杂度（最差）：O(n * log n)

TimSort的空间复杂度：O(n)

TimSort是一种稳定排序算法。

TimSort之所以能成为Java的内置排序算法之一，除了其优秀的性能，另一点就在于它的稳定性了。

我们可以对大量随机数据进行测试，虽然TimSort和快排（或者其变种）具有相同的时间复杂度【平均 O(n * log n)】，但实际数据显示快排还是要快一些的。

但是快排的缺点是它的不稳定性，比如100个人按名字进行排序，有两个叫张三的，张三(1)无序下是在张三(2)之前的，快排完后可能他们的顺序就变化了，这在某些情况下可能会有问题。

我们来看下TimSort排序动图：

图中可以清晰的看到TimSort的排序过程。

其他

在util包下除了TimSort，我们还可以看到一个类 ComparableTimSort，它是针对未实现 Comparator 接口的数据的排序版本，如Object[]。

我们对于一个int[] a，调用数组的 Arrays.sort(a)，会使用TimSort吗？

答案是否定的，对于一些基本数据类型数组，两个相同的数的前后顺序不会造成任何影响，所以Arrays.sort(a)里使用了另一种更快速的排序算法DualPivotQuicksort。

我们有时间再看一下DualPivotQuicksort这个排序。

总结

本篇文章通过对TimSort的分析，了解了TimSort的工作运行原理，对Java内置的排序算法有了更深的了解。

后面我们将看下Java的sort接口实现，看看Java内部是如何进一步优化排序，提高效率的。

参考

• JDK1.8 java.util.TimSort、java.util.ComparableTimSort源码
• JDK1.7 java.util.TimSort源码
• Python TimSort listsort.txt
• OpenJDK’s java.utils.Collection.sort() is broken:The good, the bad and the worst case?

源码地址

上述文中涉及到的代码可见于我的 GitHub