学习it的小伙伴们，在经过一段时间艰苦卓绝的努力学习后，在面试的时候总是会问些关于数据结构和算法的问题，其中算法是几乎必问的一项，因为它可以考验你的基础知识和思维逻辑能力。

算法中排序算法是最为常见的一项了,如果要说排序算法大家一般都会想到老生常谈的八大排序算法，快排，冒泡，堆排，归并等等。而有些面试官是不单单问你这些算法是如何实现的，还会问你一些这些算法的时间复杂度啊（偶尔还会问一下空间复杂度)，还有你的优化方案！这一点极其重要，如果你答的好的话会让你在面试官面前有更高的评价甚至可以因为这个优势掩蔽掉其他方面的不足！

那么如果你去面试的时候他要问你会哪些排序算法的时候？你可以怎么办？

我的建议就是先说一下我们常见的八大排序算法挑出几个自己擅长的它的时间复杂度啊它的利弊啊，之后直接放出王炸！

“以上这些排序算法都是起初编程刚刚起步时候研究出来的一些思想，经过这么多年的优化，发展到现在的已经有非常成熟的排序算法了，比如现在python的内建sort用的就是timsort排序算法，它的时间复杂度是O(n)~O(nlogn)，是目前最优的排序算法。”

好了,到现在面试官一定看你的眼神已经跟刚才不一样了，心里想：“哎哟，小伙子可以啊。看你下面怎么说。”对你接下来说的话有所期待了。下面你就要开启火力全开模式，注意~ 我要开始装✘了。

Timsort的核心过程

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

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

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

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

（2）按规则合并run

1 操作

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

1.1 run的最小长度

    run是已经排好序的一块分区。run可能会有不同的长度，Timesort根据run的长度来选择排序的策略。例如如果run的长度小于某一个值，则会选择插入排序算法来排序。run的最小长度（minrun）取决于数组的大小。当数组元素少于64个时，那么run的最小长度便是数组的长度，这是Timsort用插入排序算法来排序。当数组元素大于等于63时，对于较大的阵列，从范围32至65中选择一个称为minrun的数，使得阵列的大小除以最小run大小等于或略小于2的幂。用于此操作的最终算法只是获取数组大小的六个最高有效位，如果设置了其余任何位，则添加一个，并将该结果用作minrun。该算法适用于所有情况，包括阵列大小小于64的情况。

1.2  优化run的长度

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

1.3 合并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