世界上最快的排序算法——Timsort

转：

世界上最快的排序算法——Timsort

前言

经过60多年的发展，科学家和工程师们发明了很多排序算法，有基本的插入算法，也有相对高效的归并排序算法等，他们各有各的特点，比如归并排序性能稳定、堆排序空间消耗小等等。但是这些算法也有自己的局限性比如快速排序最坏情况和冒泡算法一样，归并排序需要消耗的空间最多，插入排序平均情况的时间复杂度太高。在实际工程应用中，我们希望得到一款综合性能最好的排序算法，能够兼具最坏和最好时间复杂度（空间复杂度的优化可以靠后毕竟内存的价格是越来越便宜），于是基于归并和插入排序的TimSort就诞生了，并且被用作Java和Python的内置排序算法。

简介

Timsort是一个自适应的、混合的、稳定的排序算法，融合了归并算法和二分插入排序算法的精髓，在现实世界的数据中有着特别优秀的表现。它是由Tim Peter于2002年发明的，用在Python这个编程语言里面。这个算法之所以快，是因为它充分利用了现实世界的待排序数据里面，有很多子串是已经排好序的不需要再重新排序，利用这个特性并且加上合适的合并规则可以更加高效的排序剩下的待排序序列。

当Timsort运行在部分排序好的数组里面的时候，需要的比较次数要远小于