前不久在这篇文章 sort与sorted的区别  中收到了这样的一个提问：“python的 sort 内部实现机制是什么？时间复杂度是多少 ”。几番Google之后有了以下的回答：

内部实现机制为：Timesort

最坏时间复杂度为：O（n log n）

空间复杂度为：O（n）

        1. （知乎）python sort 函数采用的排序算法 ：其中一个回答提到了 python 中的 sorted 排序内部实现是 timsort，并没有说 sort 。

        2. （GitHub）python的sorted排序分析 ： 同样只提到了 python 中的 sorted 排序内部实现是 timsort，并没有说 sort （知乎回答的一个链接）。

        3. （CSDN）C++，java,Python的内部实现sort怎么实现的 ：内容提到 python内部的sort采用的是混合（hybrid）排序，规模小的时候采用 binary insertion，规模大的时候采用 sample sort 。

        4. （流畅的python）list.sort 方法和 sorted 函数 ： 注7 中提到 python的排序算法——Timesort——是稳定的，意思是就算两个元素比不出大小，在每次排序的结果里他们的相对位置是固定的。

        以上大量回答都指向Timsort，那么就继续Google看看这是个啥东西

翻译自 维基百科Timesort 

    Timsort是结合了合并排序（merge sort）和插入排序（insertion sort）而得出的排序算法，它在现实中有很好的效率。Tim Peters在2002年设计了该算法并在Python中使用（TimSort 是 Python 中 list.sort 的默认实现）。该算法找到数据中已经排好序的块-分区，每一个分区叫一个run，然后按规则合并这些run。Pyhton自从2.3版以来一直采用Timsort算法排序，现在Java SE7和Android也采用Timsort算法对数组排序。

   1.1 run的最小长度

   1.2 优化run的长度

   1.3 合并run

   1.4 合并步骤

    1.5 Galloping模型

       TimSort 算法为了减少对升序部分的回溯和对降序部分的性能倒退，将输入按其升序和降序特点进行了分区。排序的输入的单位不是一个个单独的数字，而是一个个的块-分区。其中每一个分区叫一个run。针对这些 run 序列，每次拿一个 run 出来按规则进行合并。每次合并会将两个 run合并成一个 run。合并的结果保存到栈中。合并直到消耗掉所有的 run，这时将栈上剩余的 run合并到只剩一个 run 为止。这时这个仅剩的 run 便是排好序的结果。

综上述过程，Timsort算法的过程包括

（0）如何数组长度小于某个值，直接用二分插入排序算法

（1）找到各个run，并入栈

（2）按规则合并run

     现实中的大多数据通常是有部分已经排好序的，Timsort利用了这一特点。Timsort排序的输入的单位不是一个个单独的数字，而是一个个的分区。其中每一个分区叫一个“run“（图1）。针对这个 run 序列，每次拿一个 run 出来进行归并。每次归并会将两个 run 合并成一个 run。每个run最少要有2个元素。Timesor按照升序和降序划分出各个run：run如果是是升序的，那么run中的后一元素要大于或等于前一元素（a[lo]   ...），需要将run 中的元素翻转（这里注意降序的部分必须是“严格”降序才能进行翻转。因为 TimSort 的一个重要目标是保持稳定性stability。如果在 >= 的情况下进行翻转这个算法就不再是 stable）。

    run是已经排好序的一块分区。run可能会有不同的长度，Timesort根据run的长度来选择排序的策略。例如如果run的长度小于某一个值，则会选择插入排序算法来排序。run的最小长度（minrun）取决于数组的大小。当数组元素少于64个时，那么run的最小长度便是数组的长度，这是Timsort用插入排序算法来排序。当数组元素大于等于63时，For larger arrays, a number, referred to as minrun, is chosen from the range 32 to 65, such that the size of the array, divided by the minimum run size, is equal to, or slightly smaller than, a power of two. The final algorithm for this simply takes the six most significant bits of the size of the array, adds one if any of the remaining bits are set, and uses that result as the minrun. This algorithm works for all cases, including the one in which the size of the array is smaller than 64.

图1 run

       优化run的长度是指当run的长度小于minrun时，为了使这样的run的长度达到minrun的长度，会从数组中选择合适的元素插入run中。这样做使大部分的run的长度达到均衡，有助于后面run的合并操作。

       划分run和优化run长度以后，然后就是对各个run进行合并。合并run的原则是 run合并的技术要保证有最高的效率。当Timsort算法找到一个run时，会将该run在数组中的起始位置和run的长度放入栈中，然后根据先前放入栈中的run决定是否该合并run。Timsort不会合并在栈中不连续的run（Timsort does not merge non-consecutive runs because doing this would cause the element common to all three runs to become out of order with respect to the middle run.）

Timsort会合并在栈中2个连续的run。X、Y、Z代表栈最上方的3个run的长度（图2），当同时不满足下面2个条件是，X、Y这两个run会被合并，直到同时满足下面2个条件，则合并结束：

(1) X>Y+Z

(2) Y>Z

例如：如果X