V8 7.0 数组开始使用 TimSort 排序算法

[libook]

V8 Blog 原文

博客中说他们以前使用的快速排序算法在性能上并不稳定，相同长度的数组在理想情况和最差情况下的排序性能相差较大，于是改用 TimSort 算法。

这个算法是非常有名的一个算法，在保证高性能的同时还能保证性能稳定。

TimSort 的设计思路很新颖（当然也可能借鉴了其他算法）：既然单个算法会遇到最好情况和最差情况导致性能不稳定，那么是不是可以先分析数组特征，然后扬长避短在多种算法中选取合适的算法进行排序呢？

所以实际上 TimSort 是多种排序算法+分块算法+翻转，是一种“混合排序算法调度算法”。

有很多语言引擎默认使用 TimSort 作为原生排序算法，如 Python （ 2.3 开始）、Java SE 7、Android platform、GNU Octave。

[SuperMild]

据说 Python 里的 TimSort 算法实现得非常优秀（当时来说）。

[neoblackcap]

@SuperMild 因为 Python 里面的 TimSort 是 TimSort 算法作者写的，他写完之后才有 TimSort

[SuperMild]

@neoblackcap 真心牛逼

[hahastudio]

It was implemented by Tim Peters in 2002 for use in the Python programming language.

[jjx]

流畅的 Python 中有写